License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.23
URN: urn:nbn:de:0030-drops-144633
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14463/
Briański, Marcin ;
Felsner, Stefan ;
Hodor, Jędrzej ;
Micek, Piotr
Reconfiguring Independent Sets on Interval Graphs
Abstract
We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length ?(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n).
As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.
BibTeX - Entry
@InProceedings{brianski_et_al:LIPIcs.MFCS.2021.23,
author = {Bria\'{n}ski, Marcin and Felsner, Stefan and Hodor, J\k{e}drzej and Micek, Piotr},
title = {{Reconfiguring Independent Sets on Interval Graphs}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {23:1--23:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14463},
URN = {urn:nbn:de:0030-drops-144633},
doi = {10.4230/LIPIcs.MFCS.2021.23},
annote = {Keywords: reconfiguration, independent sets, interval graphs}
}
|
Keywords: |
|
reconfiguration, independent sets, interval graphs |
|
Collection: |
|
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
18.08.2021 |
