Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Siebertz, Sebastian https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-133276
URL:

; ; ;

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{lokshtanov_et_al:LIPIcs:2020:13327,
  author =	{Daniel Lokshtanov and Amer E. Mouawad and Fahad Panolan and Sebastian Siebertz},
  title =	{{On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13327},
  URN =		{urn:nbn:de:0030-drops-133276},
  doi =		{10.4230/LIPIcs.IPEC.2020.24},
  annote =	{Keywords: reconfiguration, parameterized complexity, connected dominating set, graph structure theory}
}

Keywords: reconfiguration, parameterized complexity, connected dominating set, graph structure theory
Seminar: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue date: 2020
Date of publication: 04.12.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI