Sharp Upper Bounds for Reconfiguration Sequences of Independent Sets in Trees

Publikationstyp
Conference Paper not in Proceedings
Publikationsdatum
2022-07
Sprache
English
Author
Turau, Volker 
Weyer, Christoph orcid-logo
Institut
Telematik E-17 
TORE-URI
http://hdl.handle.net/11420/14638
First published in
Leibniz international proceedings in informatics (LIPIcs) 
Citation
2nd Workshop on Combinatorial Reconfiguration, affiliated with The 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Contribution to Conference
2nd Workshop on Combinatorial Reconfiguration, affiliated with The 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
In this work we consider reconfiguration problems for independent sets using the token sliding model. For some classes of graphs efficient algorithms are known to decide whether one independent set can be transformed into the other, e.g. for cographs, claw-free graphs, and trees. Demaine et al. showed that this decision problem is solvable in O(n) time for trees with n nodes. They also proved that in this case reconfiguration sequences have length O(n^2). In particular they provided an infinite family of instances on paths for which any reconfiguration sequence has length Omega(n^2). In this work we aim at determining the maximum lengths of reconfiguration sequences for trees with n nodes and independent sets of size s. We present preliminary results and conjectures.
DDC Class
620: Ingenieurwissenschaften