On the parameterized complexity of dynamic problems with connectivity constraints

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

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

    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 feasible solution is bounded by some incrementparameter. Parameterized versions of a number of dynamic problems are studied where the solution to the base problem is assumed to be connected. We show that connectivity of solutions plays a positive role with respect to the edit-parameter by proving that the dynamic versions of Connected Dominating Set and Connected Vertex Cover are fixed-parameter tractable with respect to the edit-parameter. On the other hand, the two problems are shown to be W[2]-hard with respect to the increment-parameter. We illustrate further the utility of connected solutions by proving that Dynamic Independent Dominating Set is W[2]-hard with respect to the edit-parameter and we discuss some dynamic versions of maximization problems.
    Original languageEnglish
    Title of host publicationCombinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings
    EditorsZ Zhang, L Wu, W Xu, DZ Du
    Place of PublicationSwitzerland
    PublisherSpringer
    Pages625-636
    Number of pages12
    ISBN (Print)978-3-319-12690-6
    DOIs
    Publication statusPublished - 2014
    EventConference on Combinatorial Optimization and Applications (COCOA 2014 8th) - Maui, Hawaii, Maui, Hawaii, United States
    Duration: 19 Dec 201421 Dec 2014
    Conference number: 2014 (8th)

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume8881
    ISSN (Print)0302-9743

    Conference

    ConferenceConference on Combinatorial Optimization and Applications (COCOA 2014 8th)
    Abbreviated titleCOCOA
    CountryUnited States
    CityMaui, Hawaii
    Period19/12/1421/12/14

    Fingerprint Dive into the research topics of 'On the parameterized complexity of dynamic problems with connectivity constraints'. Together they form a unique fingerprint.

  • Cite this

    Abu-Khzam, F. N., Egan, J., Fellows, M. R., Rosamond, F. A., & Shaw, P. (2014). On the parameterized complexity of dynamic problems with connectivity constraints. In Z. Zhang, L. Wu, W. Xu, & DZ. Du (Eds.), Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings (pp. 625-636). (Lecture Notes in Computer Science; Vol. 8881). Springer. https://doi.org/10.1007/978-3-319-12691-3_47