On the parameterized complexity of dynamic problems

F.N. Abu-Khzam, J. Egan, M.R. Fellows, F.A. Rosamond, P. Shaw

    Research output: Contribution to journalArticle

    14 Downloads (Pure)

    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.
    Original languageEnglish
    Pages (from-to)426-434
    Number of pages9
    JournalTheoretical Computer Science
    Volume607
    Issue number3
    DOIs
    Publication statusPublished - 2015

      Fingerprint

    Cite this

    Abu-Khzam, F. N., Egan, J., Fellows, M. R., Rosamond, F. A., & Shaw, P. (2015). On the parameterized complexity of dynamic problems. Theoretical Computer Science, 607(3), 426-434. https://doi.org/10.1016/j.tcs.2015.06.053