On the parameterized complexity of dynamic problems with connectivity constraints

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

doi:10.1007/978-3-319-12691-3_47

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 proceeding › Conference Paper published in Proceedings › peer-review

4 Citations (Scopus)

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 language	English
Title of host publication	Combinatorial Optimization and Applications Lecture Notes in Computer Science Volume 8881 Proceedings
Editors	Z Zhang, L Wu, W Xu, DZ Du
Place of Publication	Switzerland
Publisher	Springer
Pages	625-636
Number of pages	12
ISBN (Print)	978-3-319-12690-6
DOIs	https://doi.org/10.1007/978-3-319-12691-3_47
Publication status	Published - 2014
Event	Conference on Combinatorial Optimization and Applications (COCOA 2014 8th) - Maui, Hawaii, Maui, Hawaii, United States Duration: 19 Dec 2014 → 21 Dec 2014 Conference number: 2014 (8th)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8881
ISSN (Print)	0302-9743

Conference

Conference	Conference on Combinatorial Optimization and Applications (COCOA 2014 8th)
Abbreviated title	COCOA
Country/Territory	United States
City	Maui, Hawaii
Period	19/12/14 → 21/12/14

Access to Document

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

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

@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",

note = "Conference on Combinatorial Optimization and Applications (COCOA 2014 8th), COCOA ; Conference date: 19-12-2014 Through 21-12-2014",

}

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, 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. et al.
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 proceeding › Conference Paper published in Proceedings › peer-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.

N1 - Conference code: 2014 (8th)

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

T2 - Conference on Combinatorial Optimization and Applications (COCOA 2014 8th)

Y2 - 19 December 2014 through 21 December 2014

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). doi: 10.1007/978-3-319-12691-3_47

On the parameterized complexity of dynamic problems with connectivity constraints

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this