### 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 | |

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 | United States |

City | Maui, Hawaii |

Period | 19/12/14 → 21/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