Dominating sets reconfiguration under token sliding

DOI10.1016/J.DAM.2021.05.014MaRDI QIDQ2032965zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Paul Dorbec, Paul Ouvrard

Publication date 14 June 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexitydominating setsreconfigurationtoken sliding

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let $G$ be a graph and $D_s$ and $D_t$ be two dominating sets of $G$ of size $k$. Does there exist a sequence $langle{D}_0=D_s,D_1,ldots,D_{ell-1},D_{e}ll=D_{t}angle$ of dominating sets of $G$ such that $D_{i+1}$ can be obtained from $D_i$ by replacing one vertex with one of its neighbors? In this paper, we investigate the complexity of this decision problem. We first prove that this problem is PSPACE-complete, even when restricted to split, bipartite or bounded treewidth graphs. On the other hand, we prove that it can be solved in polynomial time on dually chordal graphs (a superclass of both trees and interval graphs) or cographs.

Recommendations

• The complexity of dominating set reconfiguration
• The complexity of dominating set reconfiguration
• Reconfiguration graphs for dominating sets

Cites work

• -graphs of graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Complexity of independent set reconfigurability problems
• Connectedness of the graph of vertex-colourings
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• Distance-hereditary graphs
• Dominating sets for split and bipartite graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• Incremental optimization of independent sets under the reconfiguration framework
• Independent set reconfiguration in cographs and their generalizations
• Introduction to reconfiguration
• Linear algorithms on recursive representations of trees
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• On the complexity of reconfiguration problems
• Paths between colourings of sparse graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Shortest reconfiguration paths in the solution space of Boolean formulas
• The \(k\)-dominating graph
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The complexity of change
• The complexity of dominating set reconfiguration
• The complexity of domination problems in circle graphs
• The complexity of independent set reconfiguration on bipartite graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The domination game played on unions of graphs
• Token jumping in minor-closed classes

Cited in

(16)

• Reconfiguring dominating sets in minor-closed graph classes
• TS-reconfiguration of dominating sets in circle and circular-arc graphs
• Parameterized complexity of reconfiguration of atoms
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• The complexity of dominating set reconfiguration
• The complexity of dominating set reconfiguration
• Parameterized complexity of reconfiguration of atoms
• On solution discovery via reconfiguration
• The complexity of distance-r dominating set reconfiguration
• Independent set reconfiguration in H-free graphs
• Reconfiguration using generalized token jumping
• A survey on the parameterized complexity of reconfiguration problems
• The complexity of distance-\(r\) dominating set reconfiguration
• Parameterized complexities of dominating and independent set reconfiguration
• The tape reconfiguration problem and its consequences for dominating set reconfiguration
• Token sliding independent set reconfiguration on block graphs

This page was built for publication: Dominating sets reconfiguration under token sliding

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