2023/09/30 by Banerjee, Niranka, Hoang, Duc A.
#05C85 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2310.00241
For a fixed integer r ≥ 1, a distance-r dominating set (DrDS) of a graph G = (V, E) is a vertex subset D ⊆ V such that every vertex in V is within distance r from some member of D. Given two DrDSs Ds, Dt of G, the Distance-r Dominating Set Reconfiguration (DrDSR) problem asks if there is a sequence of DrDSs that transforms Ds into Dt (or vice versa) such that each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. The problem for r = 1 has been well-studied in the literature. We consider DrDSR for r ≥ 2 under two well-known reconfiguration rules: Token Jumping (TJ, which involves replacing a member of the current DrDS by a non-member) and Token Sliding (TS, which involves replacing a member of the current DrDS by an adjacent non-member). It is known that under any of TS and TJ, the problem on split graphs is \mathttPSPACE-complete for r = 1. We show that for r ≥ 2, the problem is in \mathttP, resulting in an interesting complexity dichotomy. Along the way, we prove some non-trivial bounds on the length of a shortest reconfiguration sequence on split graphs when r = 2 which may be of independent interest. Additionally, we design a linear-time algorithm under TJ on trees. On the negative side, we show that DrDSR for r ≥ 1 on planar graphs of maximum degree three and bounded bandwidth is \mathttPSPACE-complete, improving the degree bound of previously known results. We also show that the known \mathttPSPACE-completeness results under TS and TJ for r = 1 on bipartite graphs and chordal graphs can be extended for r ≥ 2.