EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Parameterized Complexities of Dominating and Independent Set Reconfiguration

Hans L Bodlaender iD, Carla Groenland iD, Céline M F Swennenhuis iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

Dominating set reconfigurationIndependent set reconfigurationParameterized complexityW-hierarchyXLXNLXNLP

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}
}
Kostenlos starten →