2019/10/01 by Daniel Lokshtanov, Lokshtanov, Daniel, Amer E. Mouawad +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced Graph Theory Research #Advanced Optical Network Technologies #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Enzyme Catalysis and Immobilization #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1910.00581
openalex publication_date 2019/10/01 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
In a reconfiguration version of an optimization problem \Q the\ninput is an instance of \Q and two feasible solutions S and T.\nThe objective is to determine whether there exists a step-by-step\ntransformation between S and T such that all intermediate steps also\nconstitute feasible solutions. In this work, we study the parameterized\ncomplexity of the \Connected Dominating Set Reconfiguration problem\n(\CDS-R). It was shown in previous work that the \Dominating Set\nReconfiguration problem (\DS-R) parameterized by k, the maximum\nallowed size of a dominating set in a reconfiguration sequence, is\nfixed-parameter tractable on all graphs that exclude a biclique Kd,d as a\nsubgraph, for some constant d \≥ 1. We show that the additional\nconnectivity constraint makes the problem much harder, namely, that\n\CDS-R is textsfW[1]-hard parameterized by k+\ℓ, the maximum\nallowed size of a dominating set plus the length of the reconfiguration\nsequence, already on 5-degenerate graphs. On the positive side, we show that\n\CDS-R parameterized by k is fixed-parameter tractable, and in fact\nadmits a polynomial kernel on planar graphs.\n