The Complexity of Distance-$r$ Dominating Set Reconfiguration

This paper investigates the complexity of the Distance-$r$ Dominating Set Reconfiguration problem for $r \geq 2$ under Token Jumping and Token Sliding rules, establishing a PSPACE-complete to P complexity dichotomy on split graphs, providing a linear-time algorithm for trees, and extending hardness results to planar graphs with maximum degree three and various other graph classes.

The Gist

Imagine you are playing a game of "King of the Hill" on a map of a city. You have a team of guards (tokens) placed on various street corners. Your goal is to ensure that every single house in the city is within a short walking distance of at least one guard.

In this paper, the authors are studying a specific puzzle: How do you move your team of guards from one valid arrangement to another?

Here is the breakdown of the paper using simple analogies:

1. The Rules of the Game

• The City (Graph): The map of streets and intersections.
• The Guards (Tokens): Your team members standing on corners.
• The Rule (Distance-r Dominating Set): Every house must be within $r$ steps of a guard.
  • If $r=1$, a guard must be right next to the house.
  • If $r=2$, a guard can be two streets away.
• The Moves: You can only move one guard at a time.
  • Token Sliding (TS): A guard can only walk to an immediate neighboring corner.
  • Token Jumping (TJ): A guard can teleport to any empty corner, as long as the city remains safe.

The Big Question: If you have a starting arrangement of guards ($D_s$) and a target arrangement ($D_t$), can you get from start to finish by moving guards one by one without ever leaving a house unprotected?

2. The "Hard" vs. "Easy" Switch

The authors discovered a fascinating "switch" in the difficulty of the game depending on the value of $r$.

• The Old Rule ($r=1$): When guards must be right next to the houses, the game is incredibly hard. On certain types of maps (like "split graphs" or "planar graphs"), figuring out if a solution exists is a nightmare for computers. It belongs to a class of problems called PSPACE-complete.

  • Analogy: Imagine trying to solve a maze where every wrong turn traps you forever. You might need to remember a massive amount of history to find the exit.

• The New Discovery ($r \ge 2$): The authors found that if you allow guards to be just a little further away (2 steps or more), the game suddenly becomes easy (Polynomial time) for many types of maps.

  • Analogy: It's like the guards suddenly get superpowers. Because they can reach further, they have more flexibility. The "traps" that made the $r=1$ game impossible disappear. The computer can quickly figure out a path.

The "Split Graph" Surprise:
The authors focused on a specific type of map called a "Split Graph" (think of it as a city with a dense downtown core and a sparse suburban ring).

• For $r=1$: It's a PSPACE-complete nightmare.
• For $r=2$: It becomes easy!
  This is a "complexity dichotomy"—a sharp line where the problem flips from impossible to easy just by changing the distance rule slightly.

3. The "Magic" Maps

The authors identified specific types of maps where the game is easy, even for the harder rules:

• Trees: Maps with no loops (like a family tree or a river system). They found a lightning-fast (linear time) way to solve this.
• Cographs: Maps that don't have a specific "forbidden" shape.
• Dually Chordal Graphs: A fancy mathematical category that includes trees and interval graphs.

How they did it:
For trees, they used a strategy like "cleaning up a room." They found a "canonical" (perfect) arrangement of guards and showed that no matter where your guards start, you can always slide them into that perfect arrangement, and then slide them out to your target. It's like having a universal "reset button" that simplifies the path.

4. The "Still Hard" Maps

Even though $r \ge 2$ made things easier for some maps, the authors proved it's still hard for others.

• Planar Graphs: Maps that can be drawn on a piece of paper without lines crossing (like a subway map).
• Bipartite Graphs: Maps where you can divide the city into two groups where no two people in the same group are neighbors.
• Chordal Graphs: Maps with specific "clique" structures.

Even with the "superpower" of $r \ge 2$, solving the puzzle on these maps is still a PSPACE-complete nightmare. The authors proved this by turning the guard puzzle into a logic puzzle called NCL (Nondeterministic Constraint Logic).

• Analogy: They showed that solving the guard puzzle on these maps is exactly as hard as solving a complex logic circuit where you have to flip switches to make a light turn on. If you can solve the guard puzzle, you can solve any logic circuit.

5. The "Shortest Path" Bonus

For the "Split Graphs" where the game is easy ($r=2$), the authors didn't just find a solution; they found the shortest solution.

• They proved that you never need to take more than 2 extra steps (for sliding) or 1 extra step (for jumping) compared to the absolute theoretical minimum distance between the two guard positions.
• Analogy: If you need to walk 10 blocks to get home, they proved you can definitely do it in 12 blocks or less, no matter how the city is laid out.

Summary

This paper is a map of the "difficulty landscape" for a specific graph puzzle.

1. The Twist: Increasing the reach of your guards ($r \ge 2$) turns a "hard" problem into an "easy" one for many common map types (like trees and split graphs).
2. The Limit: However, for complex, loop-filled, or highly structured maps, the problem remains a computational nightmare, even with super-powered guards.
3. The Takeaway: The authors have drawn a clear line between where computers can easily solve these reconfiguration puzzles and where they will struggle forever.

In a nutshell: "If your guards can see a little further, the puzzle gets much easier... unless your city is too complicated, in which case, good luck!"

Technical Summary

Here is a detailed technical summary of the paper "The Complexity of Distance-r Dominating Set Reconfiguration" by Niranka Banerjee and Duc A. Hoang.

1. Problem Definition

The paper investigates the Distance-$r$ Dominating Set Reconfiguration (DrDSR) problem.

• Input: A graph $G=(V, E)$, an integer $r \ge 1$, and two distance-$r$ dominating sets (DrDS), $D_s$ (source) and $D_t$ (target). A set $D \subseteq V$ is a DrDS if every vertex in $V$ is within distance $r$ of at least one vertex in $D$.
• Goal: Determine if there exists a sequence of DrDSs transforming $D_s$ into $D_t$, where each step applies a specific reconfiguration rule exactly once.
• Reconfiguration Rules:
  • Token Sliding (TS): A token (vertex in the set) moves to an adjacent unoccupied vertex.
  • Token Jumping (TJ): A token moves to any unoccupied vertex.
• Context: While the case $r=1$ (standard Dominating Set Reconfiguration) is well-studied, the complexity for $r \ge 2$ was previously unexplored.

2. Methodology

The authors employ a combination of algorithmic construction and complexity-theoretic reductions to map the complexity landscape of DrDSR across various graph classes.

• Graph Powers: They utilize the property that a set $D$ is a DrDS of $G$ if and only if it is a standard Dominating Set (DS) of the $r$-th power of the graph, $G^r$. This allows them to leverage existing results for DS on specific graph classes.
• Structural Analysis: For specific graph classes (Split graphs, Trees, Cographs), they analyze the structural constraints of DrDSs to design polynomial-time algorithms. They investigate bounds on the length of reconfiguration sequences, particularly for Split graphs.
• Hardness Reductions: To prove PSPACE-completeness, they construct polynomial-time reductions from known PSPACE-complete problems:
  • Minimum Vertex Cover Reconfiguration (Min-VCR): Used for Chordal and Bipartite graphs.
  • Nondeterministic Constraint Logic (NCL): Used to improve bounds for Planar graphs, specifically reducing from NCL on planar graphs with maximum degree 3 and bounded bandwidth.

3. Key Contributions and Results

A. Polynomial-Time Algorithms (The "Easy" Cases)

The paper establishes that for $r \ge 2$, DrDSR becomes significantly easier on several graph classes where the $r=1$ case is PSPACE-complete.

1. Split Graphs (Main Result):

   • Result: DrDSR is solvable in polynomial time for $r \ge 2$ under both TS and TJ.
   • Significance: This creates a complexity dichotomy. For $r=1$, DrDSR on split graphs is PSPACE-complete; for $r \ge 2$, it is in P.
   • Sequence Length Bounds: The authors provide tight bounds on the length of the shortest reconfiguration sequence for $r=2$ on split graphs:
     • TS: $OPT_{TS} \le M^*_{TS} + 2$, where $M^*_{TS}$ is the minimum sum of distances between matched tokens.
     • TJ: $OPT_{TJ} \le M^*_{TJ} + 1$.
     • They prove these bounds are tight by constructing specific instances requiring exactly these extra moves.

2. Dually Chordal Graphs (including Trees and Interval Graphs):

   • Result: DrDSR under TJ is solvable in quadratic time for $r \ge 2$.
   • Improvement for Trees: The authors design a linear-time algorithm ($O(n)$) for DrDSR under TJ on trees. This improves upon the quadratic bound derived from general dually chordal graphs.
   • Method: They adapt a linear-time algorithm for finding a minimum DrDS on trees (Abu-Affash et al.) to construct a partition of the tree into disjoint subtrees, ensuring a token can always be moved to a canonical minimum set.

3. Cographs:

   • Result: DrDSR is in P for $r \ge 2$ under both TS and TJ.
   • Reasoning: Connected cographs have a diameter of at most 2. For $r \ge 2$, any single vertex forms a valid DrDS, making reconfiguration trivial (any token can move to any unoccupied vertex).

B. Hardness Results (The "Hard" Cases)

The paper proves that DrDSR remains PSPACE-complete for $r \ge 1$ (and thus $r \ge 2$) on several other graph classes, often improving previous degree or bandwidth bounds.

1. Planar Graphs:

   • Result: DrDSR is PSPACE-complete for $r \ge 1$ on planar graphs with maximum degree 3 and bounded bandwidth.
   • Improvement: Previous results (Haddadan et al., Bonamy et al.) only established this for maximum degree 6. The authors achieve the tighter degree bound of 3 by reducing from the NCL problem rather than Vertex Cover.

2. Chordal Graphs:

   • Result: DrDSR is PSPACE-complete for $r \ge 2$ under both TS and TJ.
   • Note: This contrasts with the polynomial-time result for Split graphs (a subset of Chordal graphs), highlighting that the hardness arises from the specific structure of general Chordal graphs.

3. Bipartite Graphs:

   • Result: DrDSR is PSPACE-complete for $r \ge 2$ under both TS and TJ.
   • Method: An extension of the reduction used for $r=1$, involving the replacement of edges with long paths and adding a universal vertex to maintain bipartiteness.

4. Significance and Implications

• Complexity Dichotomy on Split Graphs: The most striking finding is the shift from PSPACE-complete to P for Split graphs when moving from $r=1$ to $r \ge 2$. This suggests that the "local" constraints of distance-1 domination create complex dependencies that vanish when the domination radius increases, allowing for more flexible token movement.
• Tight Bounds on Sequence Length: The analysis of the "extra moves" required for Split graphs ($+2$ for TS, $+1$ for TJ) provides deep insight into the geometry of the reconfiguration space, which is valuable for understanding the efficiency of reconfiguration algorithms.
• Improved Hardness Bounds: By reducing from NCL, the authors significantly lower the maximum degree required for PSPACE-completeness on planar graphs (from 6 to 3), bringing the theoretical hardness closer to practical graph constraints.
• Algorithmic Efficiency: The linear-time algorithm for trees under TJ is a significant practical contribution, offering an efficient solution for a fundamental class of graphs.

5. Open Questions

The authors conclude by identifying two major open problems:

1. What is the complexity of DrDSR ($r \ge 2$) under TS on trees? (Currently known for TJ).
2. What is the complexity of DrDSR ($r \ge 2$) under TS on interval graphs? (Currently known for TJ).

In summary, this paper fundamentally advances the understanding of reconfiguration problems by delineating the boundary between tractable and intractable instances for distance-$r$ domination, revealing that increasing the domination radius $r$ can drastically simplify the problem on specific graph classes while maintaining hardness on others.