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
Re-optimization
Dynamic Connected Dominating Set
DOI http://dx.doi.org/10.1016/j.tcs.2015.06.053   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 115 Abstract Views  -  Detailed Statistics
Created: Tue, 03 Nov 2015, 11:53:05 CST by Marion Farram