
Token Sliding on Split Graphs
Sikora, Florian; Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020), Token Sliding on Split Graphs, Theory of Computing Systems, 65, 4, p. 662–686. 10.1007/s00224-020-09967-8
View/ Open
Type
Article accepté pour publication ou publiéDate
2020Journal name
Theory of Computing SystemsVolume
65Number
4Publisher
Springer
Pages
662–686
Publication identifier
Metadata
Show full item recordAuthor(s)
Sikora, Florian
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Belmonte, Rémy
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kim, 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
Otachi, Yota
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 (nO(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. Finally, we study c-Colorable Reconfiguration under a relaxed rule called Token Jumping, where exchanged vertices are not required to be adjacent. We show that the problem on chordal graphs is PSPACE-complete even if c is some fixed constant. We then show that the problem is polynomial-time solvable for strongly chordal graphs even if c is a part of the input.Subjects / Keywords
GraphsRelated items
Showing items related by title and author.
-
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian (2019) Communication / Conférence
-
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2022) 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é