The complexity of dominating set reconfiguration

DOI10.1007/978-3-319-21840-3_33zbMATH Open1451.68131arXiv1503.00833OpenAlexW2582871424MaRDI QIDQ3449837FDOQ3449837

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)

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.

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

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

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)