2026-07-23T16:56:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24947 2026-02-09T08:02:27Z ddc:004 open_access

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules Hirahara, Shuichi Ohsaka, Naoto Suga, Tatsuhiro Suzuki, Akira Tamura, Yuma Zhou, Xiao combinatorial reconfiguration extended reconfiguration rule independent set reconfiguration vertex cover reconfiguration PSPACE-completeness NP-completeness In reconfiguration problems, we are given two feasible solutions to a graph problem and asked whether one can be transformed into the other via a sequence of feasible intermediate solutions under a given reconfiguration rule. While earlier work focused on modifying a single element at a time, recent studies have started examining how different rules impact computational complexity. Motivated by recent progress, we study Independent Set Reconfiguration (ISR) and Vertex Cover Reconfiguration (VCR) under the k-Token Jumping (k-TJ) and k-Token Sliding (k-TS) models. In k-TJ, up to k vertices may be replaced, while k-TS additionally requires a perfect matching between removed and added vertices. It is known that the complexity of ISR crucially depends on k, ranging from PSPACE-complete and NP-complete to polynomial-time solvable. In this paper, we further explore the gradient of computational complexity of the problems. We first show that ISR under k-TJ with k = |I| - μ remains NP-hard when μ is any fixed positive integer and the input graph is restricted to graphs of maximum degree 3 or planar graphs of maximum degree 4, where |I| is the size of feasible solutions. In addition, we prove that the problem belongs to NP not only for μ = O(1) but also for μ = O(log |I|). In contrast, we show that VCR under k-TJ is in XP when parameterized by μ = |S| - k, where |S| is the size of feasible solutions. Furthermore, we establish the PSPACE-completeness of ISR and VCR under both k-TJ and k-TS on several graph classes, for fixed k as well as superconstant k relative to the size of feasible solutions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Hirahara and Naoto Ohsaka and Tatsuhiro Suga and Akira Suzuki and Yuma Tamura and Xiao Zhou 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.39 urn:nbn:de:0030-drops-249474 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.39 eng https://creativecommons.org/licenses/by/4.0/legalcode