2026-07-26T02:16:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10252 2024-03-06T10:45:38Z ddc:004 open_access

Token Sliding on Split Graphs Belmonte, Rémy Kim, Eun Jung Lampis, Michael Mitsou, Valia Otachi, Yota Sikora, Florian reconfiguration independent set split graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rémy Belmonte and Eun Jung Kim and Michael Lampis and Valia Mitsou and Yota Otachi and Florian Sikora 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.13 urn:nbn:de:0030-drops-102529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.13 eng https://creativecommons.org/licenses/by/3.0/legalcode