• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Token Sliding on Split Graphs

Thumbnail
View/Open
LIPIcs-STACS-2019-13.pdf (503.2Kb)
Date
2019
Dewey
Principes généraux des mathématiques
Sujet
reconfiguration; independent set; split graph
DOI
http://dx.doi.org/10.4230/LIPIcs.STACS.2019.13
Conference name
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Conference date
03-2019
Conference city
Berlin
Conference country
Germany
Book title
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Author
Niedermeier, Rolf; Paul, Christophe
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Year
2019
ISBN
978-3-95977-100-9
URI
https://basepub.dauphine.fr/handle/123456789/20059
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Belmonte, Rémy
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mitsou, Valia
444497 Institut de Recherche en Informatique Fondamentale [IRIF (UMR_8243)]
Otachi, Yota
58827 Kumamoto Gakuen University
Sikora, Florian
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
13:1--13:17
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.