Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.9
URN: urn:nbn:de:0030-drops-153920
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15392/
Bodlaender, Hans L. ; Groenland, Carla ; Swennenhuis, Céline M. F.
Parameterized Complexities of Dominating and Independent Set Reconfiguration
| pdf-format: |
|
Abstract
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on the number of moves and XNL-complete when a maximum length 𝓁 for the sequence is given in binary in the input. The problems are known to be XNLP-complete when 𝓁 is given in unary instead, and W[1]- and W[2]-hard respectively when 𝓁 is also a parameter. We complete the picture by showing membership in those classes.Moreover, we show that for all the variants that we consider, token sliding and token jumping are equivalent under pl-reductions. We introduce partitioned variants of token jumping and token sliding, and give pl-reductions between the four variants that have precise control over the number of tokens and the length of the reconfiguration sequence.
BibTeX - Entry
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2021.9,
author = {Bodlaender, Hans L. and Groenland, Carla and Swennenhuis, C\'{e}line M. F.},
title = {{Parameterized Complexities of Dominating and Independent Set Reconfiguration}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {9:1--9:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-216-7},
ISSN = {1868-8969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15392},
URN = {urn:nbn:de:0030-drops-153920},
doi = {10.4230/LIPIcs.IPEC.2021.9},
annote = {Keywords: Parameterized complexity, independent set reconfiguration, dominating set reconfiguration, W-hierarchy, XL, XNL, XNLP}
}
| Keywords: | Parameterized complexity, independent set reconfiguration, dominating set reconfiguration, W-hierarchy, XL, XNL, XNLP | |
| Seminar: | 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 22.11.2021 |
