Token Sliding on Split Graphs

Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht

Titel: Token Sliding on Split Graphs

Beteiligte: Belmonte, Rémy [Verfasser:in]; Kim, Eun Jung [Verfasser:in]; Lampis, Michael [Verfasser:in]; Mitsou, Valia [Verfasser:in]; Otachi, Yota [Verfasser:in]; Sikora, Florian [Verfasser:in]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.STACS.2019.13

Schlagwörter: reconfiguration ; split graph ; independent set

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: