Charles Darwin University

CDU eSpace
Institutional Repository

CDU Staff and Student only

On the parameterized complexity of dynamic problems

Abu-Khzam, Faisal N., Egan, Judith, Fellows, Michael R., Rosamond, Frances A. and Shaw, Peter (2015). On the parameterized complexity of dynamic problems<br />. Theoretical Computer Science,607(3):426-434.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 75039815xPUB957
Title On the parameterized complexity of dynamic problems
Author Abu-Khzam, Faisal N.
Egan, Judith
Fellows, Michael R.
Rosamond, Frances A.
Shaw, Peter
Journal Name Theoretical Computer Science
Publication Date 2015
Volume Number 607
Issue Number 3
ISSN 0304-3975   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84936803984
Start Page 426
End Page 434
Total Pages 9
Place of Publication Netherlands
Publisher Elsevier BV
HERDC Category C1 - Journal Article (DIISR)
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.
Keywords Dynamic problems
Dynamic Connected Dominating Set
DOI   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
Version Filter Type
Access Statistics: 184 Abstract Views  -  Detailed Statistics
Created: Tue, 03 Nov 2015, 11:53:05 CST by Marion Farram