Show simple item record

dc.contributor.authorBelmonte, Rémy*
dc.contributor.authorKim, Eun Jung*
dc.contributor.authorLampis, Michael*
dc.contributor.authorMitsou, Valia*
dc.contributor.authorOtachi, Yota*
dc.contributor.authorSikora, Florian*
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.person.labIds*
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds444497*
hal.person.labIds58827*
hal.person.labIds989*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record