On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

Lokshtanov, Daniel and Mouawad, Amer E. and Panolan, Fahad and et al, . (2022) On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. Algorithmica, 84 (2). pp. 482-509. ISSN 0178-4617

Full text not available from this repository. (Request a copy)


In a reconfiguration version of a decision problem Q the input is an instance of Q 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 Kd,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. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Article
Additional Information: A preliminary version of this paper was accepted for publication at the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14–18, 2020, Hong Kong, China. The second author is supported by URB project “A theory of change through the lens of reconfiguration”.
Uncontrolled Keywords: Connected dominating set; Graph structure theory; Parameterized complexity; Reconfiguration
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 13 Jul 2022 10:49
Last Modified: 13 Jul 2022 10:49
URI: http://raiith.iith.ac.in/id/eprint/9676
Publisher URL: http://doi.org/10.1007/s00453-021-00909-5
OA policy: https://v2.sherpa.ac.uk/id/publication/16620
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9676 Statistics for this ePrint Item