Parameterized Complexities of Dominating and Independent Set Reconfiguration
Algorithmica · 2026-06 · 88 (3)
DOI: 10.1007/s00453-026-01381-9 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 15.04.2026. Verfasst von Hans L Bodlaender und 2 weiteren Autor:innen. Beteiligte Einrichtung: Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands. Die Arbeit nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council, Nederlandse Organisatie voor Wetenschappelijk Onderzoek.
Abstract (Originalsprache)
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, XNL-complete when a maximum length $$\ell $$ ℓ for the sequence is given in binary in the input, and XNLP-complete when $$\ell $$ ℓ is given in unary. The problems were known to be $$\textrm{W}[1]$$ W [ 1 ] - and $$\textrm{W}[2]$$ W [ 2 ] -hard respectively when $$\ell $$ ℓ 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.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands.
- Discrete Mathematics and Optimization, Technical University Delft, Delft, The Netherlands.
- PostNL, The Hague, The Netherlands.
ORCID-Profile: Hans L Bodlaender, Carla Groenland, Céline M F Swennenhuis
Förderung
- European Research Council
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Zitieren
APA
Bodlaender, H. L., Groenland, C., & Swennenhuis, C. M. F. (2026). Parameterized Complexities of Dominating and Independent Set Reconfiguration. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01381-9
Vancouver
Bodlaender HL, Groenland C, Swennenhuis CMF. Parameterized Complexities of Dominating and Independent Set Reconfiguration. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01381-9
BibTeX
@article{Bodlaender2026,
author = {Bodlaender, Hans L and Groenland, Carla and Swennenhuis, Céline M F},
title = {Parameterized Complexities of Dominating and Independent Set Reconfiguration},
journal = {Algorithmica},
year = {2026},
volume = {88},
number = {3},
doi = {10.1007/s00453-026-01381-9}
}
EUVIMED