Parameterized Complexities of Dominating and Independent Set Reconfiguration
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.
Authors
- Hans L. Bodlaender (ORCID: https://orcid.org/0000-0002-9297-3330)
- Céline M. F. Swennenhuis (ORCID: https://orcid.org/0000-0001-9654-8094)
- Carla Groenland (ORCID: https://orcid.org/0000-0002-9878-8750)
Institutions
- Utrecht University (NL)
- Computer Algorithms for Medicine (AT)
- Netherlands Nutrition Centre (NL)
- Delft University of Technology (NL)
Publication Details
- Journal
- Algorithmica
- Published
- 2026-04-15
- DOI
- https://doi.org/10.1007/s00453-026-01381-9
- Citations
- 5
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- European Commission
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- European Research Council