Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules

Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

TL;DR

This paper investigates the computational complexity of reconfiguring independent sets and vertex covers in graphs using extended rules that allow simultaneous token movements. They establish new NP-hardness results for sparse graphs and show that some problems remain in NP even for larger parameter values, while also proving PSPACE-completeness for fixed parameter values on certain graph classes.

What Problem Does This Paper Address?

Reconfiguration problems ask whether it's possible to transform one valid solution (like an independent set or vertex cover) into another through a series of intermediate valid solutions, governed by specific "reconfiguration rules." Traditional rules often involve changing one element at a time. However, real-world scenarios might require simultaneous changes. This paper focuses on "k-Token Jumping" (k-TJ) and "k-Token Sliding" (k-TS) rules, which allow up to k tokens (vertices in the solution) to be moved simultaneously. The authors explore how the complexity of reconfiguring independent sets (ISR) and vertex covers (VCR) changes with k, especially when k is related to the size of the solution (e.g., k = |I| - μ, where |I| is the initial independent set size and μ is a parameter). They aim to understand the boundaries of tractability for these problems, particularly on restricted graph classes like sparse graphs.

Methods

The paper employs a combination of techniques to establish its results:

  • Reductions: They use polynomial-time reductions from known NP-complete or PSPACE-complete problems (like EXACTLY 3-SAT, INTERNAL EXACTLY 3-SAT, NONDETERMINISTIC CONSTRAINT LOGIC, and PERFECT MATCHING RECONFIGURATION) to prove NP-hardness and PSPACE-completeness for ISR and VCR under k-TJ and k-TS.
  • Gadget Construction: For reductions, they construct specific graph structures (gadgets) that mimic the behavior of the source problem's components (e.g., clauses in SAT, edges/vertices in NCL).
  • Parameterization Analysis: They analyze the complexity of ISR and VCR when parameterized by the difference between the solution size and the number of allowed moves (k), specifically focusing on small values of this difference (μ).
  • Algorithmic Design: For VCR, they design an XP algorithm (an algorithm whose runtime is polynomial in the input size but exponential in the parameter) by utilizing a clique-compressed reconfiguration graph.
  • Combinatorial Arguments: They use combinatorial arguments, including properties of intersecting families of sets, to bound the length of reconfiguration sequences and prove membership in NP.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Sparse Graphs Matter: The NP-hardness of ISR under k-TJ persists even for graphs with maximum degree 3 or planar graphs with maximum degree 4, highlighting that sparsity doesn't necessarily lead to tractability for these problems when k is constrained.
  • NP Membership for Larger Parameters: Demonstrating that ISR can be in NP even when the parameter μ (related to how far k is from the full solution size) is as large as O(log |I|) is a significant finding, as many reconfiguration problems are PSPACE-complete due to potentially long reconfiguration sequences.
  • VCR Tractability (Parameterized): While ISR is often hard, VCR under k-TJ is shown to be in XP when parameterized by μ = |S| - k. This suggests a degree of tractability for VCR under specific parameterizations.
  • k-TJ vs. k-TS Equivalence: For certain graph classes and fixed k, the complexity of ISR under k-TJ and k-TS is shown to be equivalent, simplifying the analysis.
  • NCL Reduction Power: The reduction from Nondeterministic Constraint Logic (NCL) to ISR is a powerful technique, demonstrating how complex constraint satisfaction problems can be mapped to reconfiguration problems.

Key Results

  • NP-Hardness: ISR under k-TJ is NP-hard for graphs of maximum degree 3 (when k = |I| - μ, μ fixed) and for planar graphs of maximum degree 4 (when k = |I| - μ, μ fixed).
  • NP Membership: ISR under k-TJ is in NP for graphs with bounded chromatic number and maximum degree o(log n) when k = |I| - μ and μ = O(log |I|).
  • PSPACE-Completeness: ISR and VCR under k-TJ and k-TS are PSPACE-complete for fixed k on planar graphs of maximum degree 3 and bounded bandwidth. ISR under 2-TJ/2-TS is PSPACE-complete for line graphs.
  • XP Tractability: VCR under k-TJ is in XP when parameterized by μ = |S| - k for general graphs.
  • Superconstant k: ISR under k-TJ is PSPACE-complete for graphs of maximum degree 3 when k is superconstant relative to the initial independent set size |I| (specifically, k ≤ ε₀|I| for some constant ε₀).

Limitations and Future Work

The authors identify several open problems:

  • ISR NP-hardness on Planar Graphs: Is ISR under k-TJ NP-hard on planar graphs of maximum degree 3 for any fixed positive integer μ?
  • ISR NP Membership on General Graphs: Is ISR under k-TJ in NP on general graphs not only when μ is fixed but also when μ = O(log |I|)? (This is already addressed for specific graph classes in the paper, but the question remains for general graphs).
  • Further Parameterizations: Exploring the complexity of these problems under different parameterizations and on other graph classes remains an active area.
  • Practical Implications: While the paper focuses on theoretical complexity, understanding how these results translate to practical algorithms for reconfiguration tasks is a potential future direction.

Summary updated

BibTeX
@inproceedings{hirahara2025reachability,
  author = {Shuichi Hirahara and Naoto Ohsaka and Tatsuhiro Suga and Akira Suzuki and Yuma Tamura and Xiao Zhou},
  title = {{Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules}},
  booktitle = {ISAAC},
  year = {2025},
  doi = {10.4230/lipics.isaac.2025.39},
}

Loading related content...

Figure