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 ProceedingsResearchpeer-review

    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

    Parameterized Complexity
    Dynamic Problem
    Connectivity
    Connected Dominating Set
    Vertex Cover
    Costs
    Dominating Set
    Independent Set
    Increment

    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). Switzerland: Springer. https://doi.org/10.1007/978-3-319-12691-3_47
    Abu-Khzam, F.N. ; Egan, J. ; Fellows, M.R. ; Rosamond, F.A. ; Shaw, P. / On the parameterized complexity of dynamic problems with connectivity constraints. Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings. editor / Z Zhang ; L Wu ; W Xu ; DZ Du. Switzerland : Springer, 2014. pp. 625-636 (Lecture Notes in Computer Science).
    @inproceedings{68f4b8a155584fdcbffb18cf6d2b3ac2,
    title = "On the parameterized complexity of dynamic problems with connectivity constraints",
    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.",
    keywords = "Artificial intelligence, Computers, Connected Dominating Set, Connected vertex cover, Connectivity constraints, Dynamic problem, Feasible solution, Independent dominating set, Maximization problem, Parameterized complexity, Parameterization",
    author = "F.N. Abu-Khzam and J. Egan and M.R. Fellows and F.A. Rosamond and P. Shaw",
    year = "2014",
    doi = "10.1007/978-3-319-12691-3_47",
    language = "English",
    isbn = "978-3-319-12690-6",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "625--636",
    editor = "Z Zhang and L Wu and W Xu and DZ Du",
    booktitle = "Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings",
    address = "Switzerland",

    }

    Abu-Khzam, FN, Egan, J, Fellows, MR, Rosamond, FA & 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. Lecture Notes in Computer Science, vol. 8881, Springer, Switzerland, pp. 625-636, Conference on Combinatorial Optimization and Applications (COCOA 2014 8th), Maui, Hawaii, United States, 19/12/14. https://doi.org/10.1007/978-3-319-12691-3_47

    On the parameterized complexity of dynamic problems with connectivity constraints. / Abu-Khzam, F.N.; Egan, J.; Fellows, M.R.; Rosamond, F.A.; Shaw, P.

    Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings. ed. / Z Zhang; L Wu; W Xu; DZ Du. Switzerland : Springer, 2014. p. 625-636 (Lecture Notes in Computer Science; Vol. 8881).

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

    TY - GEN

    T1 - On the parameterized complexity of dynamic problems with connectivity constraints

    AU - Abu-Khzam, F.N.

    AU - Egan, J.

    AU - Fellows, M.R.

    AU - Rosamond, F.A.

    AU - Shaw, P.

    PY - 2014

    Y1 - 2014

    N2 - 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.

    AB - 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.

    KW - Artificial intelligence

    KW - Computers, Connected Dominating Set

    KW - Connected vertex cover

    KW - Connectivity constraints

    KW - Dynamic problem

    KW - Feasible solution

    KW - Independent dominating set

    KW - Maximization problem

    KW - Parameterized complexity, Parameterization

    UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-84921455308&doi=10.1007%2f978-3-319-12691-3_47&origin=inward&txGid=df9c2954c222c53971f8f6fed92012d5

    U2 - 10.1007/978-3-319-12691-3_47

    DO - 10.1007/978-3-319-12691-3_47

    M3 - Conference Paper published in Proceedings

    SN - 978-3-319-12690-6

    T3 - Lecture Notes in Computer Science

    SP - 625

    EP - 636

    BT - Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings

    A2 - Zhang, Z

    A2 - Wu, L

    A2 - Xu, W

    A2 - Du, DZ

    PB - Springer

    CY - Switzerland

    ER -

    Abu-Khzam FN, Egan J, Fellows MR, Rosamond FA, Shaw P. On the parameterized complexity of dynamic problems with connectivity constraints. In Zhang Z, Wu L, Xu W, Du DZ, editors, Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings. Switzerland: Springer. 2014. p. 625-636. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-12691-3_47