The complexity of dominating set reconfiguration

DOI10.1007/978-3-319-21840-3_33MaRDI QIDQ3449837zbMATH OpenOpenAlexFDO

Authors Arash Haddadan, Takehiro Ito, Amer E. Mouawad, N. Nishimura, Hirotaka Ono, Akira Suzuki, Youcef Tebbal

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00833

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$. Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each dominating set in the sequence is of cardinality at most $k$ and can be obtained from the previous one by either adding or deleting exactly one vertex. This problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, trees, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence such that the number of additions and deletions is bounded by $O(n)$, where $n$ is the number of vertices in the input graph.

Recommendations

• The complexity of dominating set reconfiguration
• Dominating sets reconfiguration under token sliding
• On the parameterized complexity of reconfiguration of connected dominating sets

Cites work

• Complexity of independent set reconfigurability problems
• Dominating sets for split and bipartite graphs
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration of vertex covers in a graph
• The \(k\)-dominating graph
• The complexity of change
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Vertex Cover Reconfiguration and Beyond

Cited in

(13)

• Reconfiguring minimum dominating sets: the -graph of a tree
• Reconfiguration on nowhere dense graph classes
• Dominating sets reconfiguration under token sliding
• Reconfiguring dominating sets in minor-closed graph classes
• Reconfiguration graphs for dominating sets
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• Rerouting shortest paths in planar graphs
• On the structure of dominating graphs
• Reconfiguration of vertex covers in a graph
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• The complexity of dominating set reconfiguration
• On the complexity of distance-\(d\) independent set reconfiguration
• On the parameterized complexity of reconfiguration of connected dominating sets

This page was built for publication: The complexity of dominating set reconfiguration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449837)