×

Token sliding on chordal graphs. (English) Zbl 1483.05173

Bodlaender, Hans L. (ed.) et al., Graph-theoretic concepts in computer science. 43rd international workshop, WG 2017, Eindhoven, The Netherlands, June 21–23, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10520, 127-139 (2017).
Summary: Let \(I\) be an independent set of a graph \(G\). Imagine that a token is located on every 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 single token move. This problem is known to be PSPACE-complete even on planar graphs.
In [Lect. Notes Comput. Sci. 8889, 389–400 (2014; Zbl 1435.05189)], E. D. Demaine et al. asked whether the Token Sliding problem can be decided in polynomial time on interval graphs and more generally on chordal graphs. T. Yamada and R. Uehara [Lect. Notes Comput. Sci. 9627, 236–248 (2016; Zbl 1475.68254)] showed 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 an independent set \(I\) of an interval graph can be transformed into another independent set \(J\). Moreover, 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 latter 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.
For the entire collection see [Zbl 1374.68006].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv