Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Token Sliding on Chordal Graphs
verfasst von : Marthe Bonamy, Nicolas Bousquet
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 [9], Demaine et al. asked whether the Token Sliding problem can be decided in polynomial time on interval graphs and more generally on chordal graphs. Yamada and Uehara [20] 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.