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.
Recommendations
Cited in
(30)- Polynomial-time algorithm for sliding tokens on trees
- Extremal independent set reconfiguration
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- On girth and the parameterized complexity of token sliding and token jumping
- Token sliding on split graphs
- Feedback vertex set reconfiguration in planar graphs
- On reconfiguration graphs of independent sets under token sliding
- 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
- Invitation to combinatorial reconfiguration
- On finding short reconfiguration sequences between independent sets
- Sliding tokens on block graphs
- Sliding tokens on a cactus
- On the complexity of distance-\(d\) independent set reconfiguration
- scientific article; zbMATH DE number 7525461 (Why is no real title available?)
- scientific article; zbMATH DE number 7765402 (Why is no real title available?)
- Linear-time algorithm for sliding tokens on trees
- Reconfiguration of colorable sets in classes of perfect graphs
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Galactic token sliding
- 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
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)
