License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.13
URN: urn:nbn:de:0030-drops-102529
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10252/
Go to the corresponding LIPIcs Volume Portal

Belmonte, Rémy ; Kim, Eun Jung ; Lampis, Michael ; Mitsou, Valia ; Otachi, Yota ; Sikora, Florian

Token Sliding on Split Graphs

pdf-format:
LIPIcs-STACS-2019-13.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{belmonte_et_al:LIPIcs:2019:10252,
  author =	{R{\'e}my Belmonte and Eun Jung Kim and Michael Lampis and Valia Mitsou and Yota Otachi and Florian Sikora},
  title =	{{Token Sliding on Split Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10252},
  doi =		{10.4230/LIPIcs.STACS.2019.13},
  annote =	{Keywords: reconfiguration, independent set, split graph}
}

Keywords: reconfiguration, independent set, split graph
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI