Parameterized Complexities of Dominating and Independent Set Reconfiguration

Area of Science:

• Computational Complexity Theory
• Graph Theory
• Discrete Mathematics

Background:

• Independent Set Reconfiguration and Dominating Set Reconfiguration are key problems in computational complexity.
• Previous research established W[1]-hardness and W[2]-hardness for certain variants, leaving a gap in understanding their full parameterized complexity.

Purpose of the Study:

• To determine the precise parameterized complexity of various independent set and dominating set reconfiguration problems.
• To establish the relationship between token sliding and token jumping reconfiguration variants.
• To introduce and analyze partitioned variants of token sliding and token jumping.

Main Methods:

• Parameterized complexity analysis using complexity classes XL, XNL, and XNLP.
• Establishing pl-reductions between different reconfiguration variants.
• Analyzing the impact of input encoding (binary vs. unary) for the maximum sequence length parameter.

Main Results:

• Both independent set reconfiguration and dominating set reconfiguration are shown to be XL-complete (no move limit), XNL-complete (binary input for length limit ℓ), and XNLP-complete (unary input for length limit ℓ).
• Membership in W[1] and W[2] classes is proven for the respective parameterized problems.
• Token sliding and token jumping are demonstrated to be equivalent under pl-reductions across all considered variants.
• Partitioned variants of token jumping and sliding were introduced, with pl-reductions established between them.

Conclusions:

• The parameterized complexity landscape for independent set and dominating set reconfiguration is now fully settled.
• The equivalence of token sliding and token jumping simplifies the study of reconfiguration problems.
• The introduction of partitioned variants offers new avenues for precise control over reconfiguration sequences and token counts.