Token sliding on chordal graphs
From MaRDI portal
Publication:1687909
DOI10.1007/978-3-319-68705-6_10zbMATH Open1483.05173arXiv1605.00442OpenAlexW2345745843MaRDI QIDQ1687909FDOQ1687909
Authors: Marthe Bonamy, Nicolas Bousquet 
Publication date: 4 January 2018
Abstract: Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms I into J so that every pair of consecutive independent sets of the sequence can be obtained via a token move. This problem is known to be PSPACE-complete even on planar graphs. In 2014, Demaine et al. asked whether the Token Sliding reconfiguration problem is polynomial time solvable on interval graphs and more generally in chordal graphs. Yamada and Uehara showed in 2016 that a polynomial time transformation can be found in proper interval graphs. In this paper, we answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether two independent sets of an interval graph are in the same connected component. Moveover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of k-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs.
Full work available at URL: https://arxiv.org/abs/1605.00442
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (30)
- Polynomial-time algorithm for sliding tokens on trees
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- On girth and the parameterized complexity of token sliding and token jumping
- Feedback vertex set reconfiguration in planar graphs
- On reconfiguration graphs of independent sets under token sliding
- Token sliding on split graphs
- Token sliding on split graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguration of Spanning Trees with Many or Few Leaves
- Token sliding on graphs of girth five
- Parameterized complexity of independent set reconfiguration problems
- Reconfiguration of connected graph partitions
- Introduction to reconfiguration
- Token sliding on graphs of girth five
- On finding short reconfiguration sequences between independent sets
- Invitation to combinatorial reconfiguration
- Sliding tokens on block graphs
- Sliding tokens on a cactus
- On the complexity of distance-\(d\) independent set reconfiguration
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reconfiguration of colorable sets in classes of perfect graphs
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Galactic token sliding
- Linear-time algorithm for sliding tokens on trees
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- Incremental optimization of independent sets under the reconfiguration framework
- Reconfiguration of cliques in a graph
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
- Extremal independent set reconfiguration
This page was built for publication: Token sliding on chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1687909)
