For a fixed integer \(r \ge 1\) , a distance-r dominating set of a graph \(G = (V, E)\) is a vertex subset \(D \subseteq V\) such that every vertex in V is within distance r from some member of D. Given two distance-r dominating sets \(D_s, D_t\) of G, the Distance-r Dominating Set Reconfiguration (D r DSR) problem asks if there is a sequence of distance-r dominating sets that transforms \(D_s\) into \(D_t\) (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 D r DSR for \(r \ge 2\) under two well-known reconfiguration rules: Token Jumping ( \(\textsf{TJ}\) , which involves replacing a member of the current DrDS by a non-member) and Token Sliding ( \(\textsf{TS}\) , which involves replacing a member of the current DrDS by an adjacent non-member). It is known that under any of \(\textsf{TS}\) and \(\textsf{TJ}\) , the problem on split graphs is \(\texttt{PSPACE}\) -complete for \(r = 1\) . We show that for \(r \ge 2\) , the problem is in \(\texttt{P}\) , 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 prove some observations that lead to the polynomial-time solvability of D r DSR for \(r \ge 2\) on dually chordal graphs under \(\textsf{TJ}\) and on cographs under any of \(\textsf{TS}\) and \(\textsf{TJ}\) , and design a linear-time algorithm for solving the problem under \(\textsf{TJ}\) on trees. On the negative side, we show that D r DSR for \(r \ge 1\) on planar graphs of maximum degree three and bounded bandwidth is \(\texttt{PSPACE}\) -complete, improving the degree bound of previously known results. We also show that the known \(\texttt{PSPACE}\) -completeness results under \(\textsf{TS}\) and \(\textsf{TJ}\) for \(r = 1\) on bipartite graphs and chordal graphs can be extended for \(r \ge 2\) .

The Complexity of Distance-r Dominating Set Reconfiguration

会议论文
发表日期：

2025年

查看全文

Niranka Banerjee,
Duc A. Hoang

摘要

For a fixed integer \(r \ge 1\) , a distance-r dominating set of a graph \(G = (V, E)\) is a vertex subset \(D \subseteq V\) such that every vertex in V is within distance r from some member of D. Given two distance-r dominating sets \(D_s, D_t\) of G, the Distance-r Dominating Set Reconfiguration (D r DSR) problem asks if there is a sequence of distance-r dominating sets that transforms \(D_s\) into \(D_t\) (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 D r DSR for \(r \ge 2\) under two well-known reconfiguration rules: Token Jumping ( \(\textsf{TJ}\) , which involves replacing a member of the current DrDS by a non-member) and Token Sliding ( \(\textsf{TS}\) , which involves replacing a member of the current DrDS by an adjacent non-member). It is known that under any of \(\textsf{TS}\) and \(\textsf{TJ}\) , the problem on split graphs is \(\texttt{PSPACE}\) -complete for \(r = 1\) . We show that for \(r \ge 2\) , the problem is in \(\texttt{P}\) , 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 prove some observations that lead to the polynomial-time solvability of D r DSR for \(r \ge 2\) on dually chordal graphs under \(\textsf{TJ}\) and on cographs under any of \(\textsf{TS}\) and \(\textsf{TJ}\) , and design a linear-time algorithm for solving the problem under \(\textsf{TJ}\) on trees. On the negative side, we show that D r DSR for \(r \ge 1\) on planar graphs of maximum degree three and bounded bandwidth is \(\texttt{PSPACE}\) -complete, improving the degree bound of previously known results. We also show that the known \(\texttt{PSPACE}\) -completeness results under \(\textsf{TS}\) and \(\textsf{TJ}\) for \(r = 1\) on bipartite graphs and chordal graphs can be extended for \(r \ge 2\) .