For a fixed integer <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$r \ge 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, a distance-r dominating set of a graph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$G = (V, E)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is a subset <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$D \subseteq V$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>⊆</mo> <mi>V</mi> </mrow> </math></EquationSource> </InlineEquation> such that every vertex in V is within distance r from some member of D. Given two distance-r dominating sets <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$D_s$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>D</mi> <mi>s</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$D_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>D</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation> of G, the Distance-r Dominating Set Reconfiguration (Dr DSR) problem asks whether there exists a sequence of distance-r dominating sets transforming <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$D_s$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>D</mi> <mi>s</mi> </msub> </math></EquationSource> </InlineEquation> into <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$D_t$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>D</mi> <mi>t</mi> </msub> </math></EquationSource> </InlineEquation>, where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. The case when <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$r = 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> has been extensively studied in the literature. We study Dr DSR for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$r \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> under two well-known reconfiguration rules: Token Jumping (<InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\textsf{TJ}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TJ</mi> </math></EquationSource> </InlineEquation>), which involves replacing a member of the current DrDS with a non-member, and Token Sliding (<InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\textsf{TS}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TS</mi> </math></EquationSource> </InlineEquation>), which involves replacing a member of the current DrDS with an adjacent non-member. For <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$r = 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, it is known that under either <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\textsf{TS}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TS</mi> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\textsf{TJ}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TJ</mi> </math></EquationSource> </InlineEquation>, the problem on split graphs is <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\texttt{PSPACE}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="monospace">PSPACE</mi> </math></EquationSource> </InlineEquation>-complete. We show that for <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$r \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, the problem is in <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\texttt{P}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="monospace">P</mi> </math></EquationSource> </InlineEquation>, resulting in an interesting complexity dichotomy. Along the way, we establish nontrivial bounds on the length of a shortest reconfiguration sequence on split graphs when <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$r = 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, which may be of independent interest. Moreover, we provide observations that lead to polynomial-time algorithms for Dr DSR for <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$r \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> on dually chordal graphs under <InlineEquation ID="IEq20"> <EquationSource Format="TEX">$\textsf{TJ}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TJ</mi> </math></EquationSource> </InlineEquation> and on cographs under either <InlineEquation ID="IEq21"> <EquationSource Format="TEX">$\textsf{TS}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TS</mi> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq22"> <EquationSource Format="TEX">$\textsf{TJ}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TJ</mi> </math></EquationSource> </InlineEquation>. We also design a linear-time algorithm for solving the problem under <InlineEquation ID="IEq23"> <EquationSource Format="TEX">$\textsf{TJ}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TJ</mi> </math></EquationSource> </InlineEquation> on trees. On the negative side, we prove that Dr DSR for <InlineEquation ID="IEq24"> <EquationSource Format="TEX">$r \ge 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> remains <InlineEquation ID="IEq25"> <EquationSource Format="TEX">$\texttt{PSPACE}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="monospace">PSPACE</mi> </math></EquationSource> </InlineEquation>-complete on planar graphs of maximum degree three and bounded bandwidth, improving the degree bound of previously known results. We further demonstrate that the known <InlineEquation ID="IEq26"> <EquationSource Format="TEX">$\texttt{PSPACE}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="monospace">PSPACE</mi> </math></EquationSource> </InlineEquation>-completeness results under <InlineEquation ID="IEq27"> <EquationSource Format="TEX">$\textsf{TS}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TS</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq28"> <EquationSource Format="TEX">$\textsf{TJ}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">TJ</mi> </math></EquationSource> </InlineEquation> on bipartite graphs and chordal graphs for <InlineEquation ID="IEq29"> <EquationSource Format="TEX">$r = 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> can be extended to <InlineEquation ID="IEq30"> <EquationSource Format="TEX">$r \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>.

The complexity of distance-r dominating set reconfiguration

期刊论文
发表日期：

2026年3月7日

查看全文

Niranka Banerjee,
Duc A. Hoang

摘要

For a fixed integer $r \ge 1$ $r \geq 1$ , a distance-r dominating set of a graph $G = (V, E)$ $G = (V, E)$ is a subset $D \subseteq V$ $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_{s}$ and $D_t$ $D_{t}$ of G, the Distance-r Dominating Set Reconfiguration (Dr DSR) problem asks whether there exists a sequence of distance-r dominating sets transforming $D_s$ $D_{s}$ into $D_t$ $D_{t}$ , where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. The case when $r = 1$ $r = 1$ has been extensively studied in the literature. We study Dr DSR for $r \ge 2$ $r \geq 2$ under two well-known reconfiguration rules: Token Jumping ( $\textsf{TJ}$ $TJ$ ), which involves replacing a member of the current DrDS with a non-member, and Token Sliding ( $\textsf{TS}$ $TS$ ), which involves replacing a member of the current DrDS with an adjacent non-member. For $r = 1$ $r = 1$ , it is known that under either $\textsf{TS}$ $TS$ or $\textsf{TJ}$ $TJ$ , the problem on split graphs is $\texttt{PSPACE}$ $PSPACE$ -complete. We show that for $r \ge 2$ $r \geq 2$ , the problem is in $\texttt{P}$ $P$ , resulting in an interesting complexity dichotomy. Along the way, we establish nontrivial bounds on the length of a shortest reconfiguration sequence on split graphs when $r = 2$ $r = 2$ , which may be of independent interest. Moreover, we provide observations that lead to polynomial-time algorithms for Dr DSR for $r \ge 2$ $r \geq 2$ on dually chordal graphs under $\textsf{TJ}$ $TJ$ and on cographs under either $\textsf{TS}$ $TS$ or $\textsf{TJ}$ $TJ$ . We also design a linear-time algorithm for solving the problem under $\textsf{TJ}$ $TJ$ on trees. On the negative side, we prove that Dr DSR for $r \ge 1$ $r \geq 1$ remains $\texttt{PSPACE}$ $PSPACE$ -complete on planar graphs of maximum degree three and bounded bandwidth, improving the degree bound of previously known results. We further demonstrate that the known $\texttt{PSPACE}$ $PSPACE$ -completeness results under $\textsf{TS}$ $TS$ and $\textsf{TJ}$ $TJ$ on bipartite graphs and chordal graphs for $r = 1$ $r = 1$ can be extended to $r \ge 2$ $r \geq 2$ .