Show simple item record

hal.structure.identifier
dc.contributor.authorBelmonte, Rémy*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887
*
hal.structure.identifierInstitut de Recherche en Informatique Fondamentale [IRIF (UMR_8243)]
dc.contributor.authorMitsou, Valia*
hal.structure.identifierKumamoto Gakuen University
dc.contributor.authorOtachi, Yota*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorSikora, Florian
HAL ID: 742949
ORCID: 0000-0003-2670-6258
*
dc.date.accessioned2019-10-09T11:09:07Z
dc.date.available2019-10-09T11:09:07Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20059
dc.language.isoenen
dc.subjectreconfigurationen
dc.subjectindependent seten
dc.subjectsplit graphen
dc.subject.ddc511en
dc.titleToken Sliding on Split Graphsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages13:1--13:17en
dc.relation.ispartoftitle36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)en
dc.relation.ispartofeditorNiedermeier, Rolf
dc.relation.ispartofeditorPaul, Christophe
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofdate2019
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-95977-100-9en
dc.relation.conftitle36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)en
dc.relation.confdate2019-03
dc.relation.confcityBerlinen
dc.relation.confcountryGermanyen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.STACS.2019.13en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-10-09T10:54:43Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record