Name
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 -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 -hard with respect to the increment-parameter. Moreover, we show that Dynamic Independent Dominating Set is 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 -hard if the increment-parameter is replaced with the reoptimization parameter.Finally, we establish that Dynamic Dominating Set becomes 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.06.053 | Theoretical Computer Science |
Keywords | Field | DocType |
Dynamic problems,Re-optimization,Dynamic Connected Dominating Set,Parameterized complexity | Discrete mathematics,Combinatorics,Parameterized complexity,Dominating set,Clique,Cardinality,Vertex cover,Connected dominating set,Dynamic problem,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
607 | P3 | 0304-3975 |
Citations | PageRank | References |
5 | 0.45 | 13 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Faisal N. Abu Khzam | 1 | 404 | 36.25 |
| Judith Egan | 2 | 5 | 0.78 |
| Michael R. Fellows | 3 | 4138 | 319.37 |
| Frances A. Rosamond | 4 | 21 | 2.83 |
| Peter Shaw | 5 | 92 | 6.34 |