On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
| Autor: | Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
graph structure theory General Computer Science Discrete Mathematics (cs.DM) reconfiguration Applied Mathematics Computational Complexity (cs.CC) Computer Science Applications connected dominating set Computer Science - Computational Complexity Theory of computation → Graph algorithms analysis Computer Science - Data Structures and Algorithms FOS: Mathematics Theory of computation → Parameterized complexity and exact algorithms Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) parameterized complexity Computer Science - Discrete Mathematics |
| Popis: | In a reconfiguration version of a decision problem 𝒬 the input is an instance of 𝒬 and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K_{d,d} as a subgraph, for some constant d ≥ 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k+𝓁, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs. LIPIcs, Vol. 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), pages 24:1-24:15 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|