## Abstract

In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a solution is bounded by some increment-parameter.

Capitalizing on the recent initial work of Downey et al. on the Dynamic Dominating Set problem, we launch a study of the dynamic versions of a number of problems including Vertex Cover, Maximum Clique, Connected Vertex Cover and Connected Dominating Set. In particular, we show that Dynamic Vertex Cover is W[1]W[1]-hard, and the connected versions of both Dynamic Vertex Cover and Dynamic Dominating Set become fixed-parameter tractable with respect to the edit-parameter while they remain W[2]W[2]-hard with respect to the increment-parameter. Moreover, we show that Dynamic Independent Dominating Set is W[2]W[2]-hard with respect to the edit-parameter.

We introduce the reoptimization parameter, which bounds the difference between the cardinalities of initial and target solutions. We prove that, while Dynamic Maximum Clique is fixed-parameter tractable with respect to the edit-parameter, it becomes W[1]W[1]-hard if the increment-parameter is replaced with the reoptimization parameter.

Finally, we establish that Dynamic Dominating Set becomes W[2]W[2]-hard when the target solution is required not to be larger than the initial one, even if the edit parameter is exactly one.

Capitalizing on the recent initial work of Downey et al. on the Dynamic Dominating Set problem, we launch a study of the dynamic versions of a number of problems including Vertex Cover, Maximum Clique, Connected Vertex Cover and Connected Dominating Set. In particular, we show that Dynamic Vertex Cover is W[1]W[1]-hard, and the connected versions of both Dynamic Vertex Cover and Dynamic Dominating Set become fixed-parameter tractable with respect to the edit-parameter while they remain W[2]W[2]-hard with respect to the increment-parameter. Moreover, we show that Dynamic Independent Dominating Set is W[2]W[2]-hard with respect to the edit-parameter.

We introduce the reoptimization parameter, which bounds the difference between the cardinalities of initial and target solutions. We prove that, while Dynamic Maximum Clique is fixed-parameter tractable with respect to the edit-parameter, it becomes W[1]W[1]-hard if the increment-parameter is replaced with the reoptimization parameter.

Finally, we establish that Dynamic Dominating Set becomes W[2]W[2]-hard when the target solution is required not to be larger than the initial one, even if the edit parameter is exactly one.

Original language | English |
---|---|

Pages (from-to) | 426-434 |

Number of pages | 9 |

Journal | Theoretical Computer Science |

Volume | 607 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2015 |