
Token Sliding on Split Graphs
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian (2019), Token Sliding on Split Graphs, in Niedermeier, Rolf; Paul, Christophe, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 13:1--13:17. 10.4230/LIPIcs.STACS.2019.13
View/ Open
Type
Communication / ConférenceDate
2019Conference title
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)Conference date
2019-03Conference city
BerlinConference country
GermanyBook title
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)Book author
Niedermeier, Rolf; Paul, ChristophePublisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISBN
978-3-95977-100-9
Pages
13:1--13:17
Publication identifier
Metadata
Show full item recordAuthor(s)
Belmonte, RémyKim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mitsou, Valia
Institut de Recherche en Informatique Fondamentale [IRIF (UMR_8243)]
Otachi, Yota
Kumamoto Gakuen University
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the c-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set c-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed c >= 1 on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time (n^{O(c)}) algorithm for all fixed values of c, except c=1, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that c-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by c and the length of the solution, as well as a tight ETH-based lower bound for both parameters.Subjects / Keywords
reconfiguration; independent set; split graphRelated items
Showing items related by title and author.
-
Sikora, Florian; Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Article accepté pour publication ou publié
-
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Communication / Conférence
-
Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2017) Communication / Conférence
-
Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2022) Article accepté pour publication ou publié
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié