<p><a href="http://arxiv.org/abs/0907.4283">Dawar and Kreutzer</a> have shown that the problem is fixed-parameter tractable on nowhere dense classes of graphs, which includes the planar graphs, the graphs of bounded (local) tree-width and all classes with (locally) excluded minors. </p>

<p><a href="http://arxiv.org/abs/1110.5190">Dvorak</a> has shown that there is a polynomial time constant factor approximation for classes of bounded expansion, which includes the planar graphs, graphs of bounded tree-width and all classes with excluded minors. </p>

CC BY-SA 3.0
2013-11-08T11:52:18.830Z
2013-11-08T11:52:18.830Z
Sebastian Siebertz
<p>It is quite easy to do dynamic programming on graphs of treewidth $k$ for this problem.
One can keep for each vertex in a bag the shortest distance to some vertex in the partial solution and the distance to future solution needed to dominate the undominated vertices.</p>

<p>This in total gives a table size of $O(r^k)$ so for fixed $r$ this problem is FPT parameterized by treewidth, however if $r$ is not fixed this becomes an XP algorithm.
As far as I know the question of whether this problem is FPT for all values of $r$ is open.</p>

CC BY-SA 3.0
2017-04-04T11:20:13.470Z
Maybe change $r^k$ to $r^{O(k)}$?
daniello
CC BY-SA 3.0
2013-11-05T23:09:11.623Z
2013-11-05T23:09:11.623Z
Martin Vatshelle
<p>There is a recent paper by Glencora Borradaile, Hung Le: <a href="http://drops.dagstuhl.de/opus/volltexte/2017/6919/" rel="noreferrer">Optimal Dynamic Program for r-Domination Problems over Tree Decompositions</a> (IPEC 2016). Here they show that there is an algorithm that given as input a graph $G$, an integer $r$, and a tree-decomposition of $G$ of width $w$, computes an optimal $r$-dominating set of $G$ in time $O((2r+1)^wn)$.
Furthermore, they show that this is the best one can do, in the following sense: an algorithm with running time $O((2r+1-\epsilon)^wn^{O(1)})$ for $\epsilon &gt; 0$ would contradict the Strong Exponential Time Hypothesis.</p>

CC BY-SA 3.0
2017-03-29T21:11:17.830Z
2017-03-29T21:11:17.830Z
daniello
<p>A linear sequential algorithm to compute a optimal r-domination for a tree is due to Slater:</p>

<p>P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976.
doi:10.1145/321958.321964</p>

<p>A distributed algorithm for the same setting is due to Turau and Köhler: </p>

<p>Volker Turau and Sven Köhler. A Distributed Algorithm for Minimum Distance-k Domination in Trees. Journal of Graph Algorithms and Applications, 19(1):223–242,5  (see <a href="http://jgaa.info/getPaper?id=354" rel="nofollow noreferrer">http://jgaa.info/getPaper?id=354</a>)</p>

CC BY-SA 3.0
2017-03-30T10:52:56.730Z
2017-03-30T10:52:56.730Z
Volker Turau
<p>An (optimal) $r$-domination for $G$ is an (optimal) domination for the $r$th power $G^r$ and vice versa 
($G^r$ is obtained from $G$ by adding new edges between distinct vertices of distance at most $r$).</p>

<p>The following facts are well known: (1) All powers of a strongly chordal graph are strongly chordal 
(A. Lubiw, Master thesis; see also Dahlhaus &amp; Duchet, On strongly chordal graphs, 
Ars Combin. 24 B (1987) 23-30), and (2) Domination is solvable in linear time for strongly chordal graphs 
(M. Farber. Domination, independent domination and duality in strongly chordal graphs, 
Discrete Appl. Math., 7 (1984) 115–130). Hence $r$-domination is solvable in polynomial time for 
strongly chordal graphs, in particular for trees ($r$ fixed or not).</p>

<p>Gurski &amp; Wanke proved in <a href="http://www.sciencedirect.com/science/article/pii/S0166218X08004022">this paper</a> 
that the clique-width of $G^r$ is at most $2\cdot (r+1)^{\text{tw}(G)+1}−2$, where $\text{tw}(G)$ is the tree-width 
of $G$. Thus, for fixed $r$, the $r$th powers of bounded tree-width graphs have bounded clique-width. 
Hence, for fixed $r$, $r$-domination is solvable in polynomial time for bounded tree-width graphs 
(by Courcelle's theorem).    </p>

CC BY-SA 3.0
2013-11-07T16:50:10.380Z
2013-11-07T16:50:10.380Z
vb le
<p>Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$, while minimizing the size of $S$. </p>

<p>From what I have checked so far, I got the following: There is this related problem of finding a $(k,r)$-center in a graph which is a subset $S$ of size at most $k$ such that all the vertices in the graph are at a distance of atmost $r$ from some vertex in $S$(here both $|S| \leq k$ and $r$ are parts of the input) for which <a href="https://www.google.co.in/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CCgQFjAA&amp;url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3709&amp;rep=rep1&amp;type=pdf&amp;ei=aCV5UqbiIsqErAfVwoDYDw&amp;usg=AFQjCNEgry8oI-5qLowdUGlrR3fa5eL4Qg">Demaine et al</a>. have a FPT algorithm for planar graphs. Otherwise the problem is $W[2]$-hard for even $r = 1$.</p>

<p>Is anything known about the exact complexity of $r$-domination problem for bounded tree width graphs or even just trees? (Is $r$-domination MSO definable? the usual $k$-dominating set problem is MSO definable -- which then would allow one to use Courcelle's theorem to conclude that there is a linear time algorithm for the problem). Are there any conditional hardness results known regarding this problem?</p>

CC BY-SA 3.0
2013-11-05T18:53:02.953Z
An optimal $r$-domination for $G$ is an optimal domination for the $r$th power $G^r$ and vice versa. So, the $r$-domination problem is solvable in polynomial time for trees and, more general, for bounded tree-width graphs.
vb le
CC BY-SA 3.0
2013-11-06T09:39:39.807Z
@vble I guess $r$ is fixed. But why is the $r$-domination problem solvable for bounded tree width graphs? the power of such graphs have unbounded tree width.
Peng O
CC BY-SA 3.0
2013-11-06T12:03:35.990Z
Yes, $r$ is fixed, thanks. Yes, $G^r$ has unbounded tree-width but **bounded clique-width** (due to Gurski and Wanke) and the usual domination problem is MSO definable.
vb le
CC BY-SA 3.0
2013-11-07T13:01:30.267Z
@vble Thanks! Can you provide references and make your comment an answer?
Nikhil
CC BY-SA 3.0
2013-11-07T16:52:31.753Z
@ Nikhil: done.
vb le
<graph-algorithms><np-hardness><treewidth><parameterized-complexity><fixed-parameter-tractable>
Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs
Nikhil
# Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

(Asked by: username_0 on 2013-11-05)

Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$, while minimizing the size of $S$.

From what I have checked so far, I got the following: There is this related problem of finding a $(k,r)$-center in a graph which is a subset $S$ of size at most $k$ such that all the vertices in the graph are at a distance of atmost $r$ from some vertex in $S$(here both $|S| \leq k$ and $r$ are parts of the input) for which [Demaine et al](https://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCgQFjAA&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3709&rep=rep1&type=pdf&ei=aCV5UqbiIsqErAfVwoDYDw&usg=AFQjCNEgry8oI-5qLowdUGlrR3fa5eL4Qg). have a FPT algorithm for planar graphs. Otherwise the problem is $W[2]$-hard for even $r = 1$.

Is anything known about the exact complexity of $r$-domination problem for bounded tree width graphs or even just trees? (Is $r$-domination MSO definable? the usual $k$-dominating set problem is MSO definable -- which then would allow one to use Courcelle's theorem to conclude that there is a linear time algorithm for the problem). Are there any conditional hardness results known regarding this problem?

**Tags:** graph-algorithms, np-hardness, treewidth, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: An optimal $r$-domination for $G$ is an optimal domination for the $r$th power $G^r$ and vice versa. So, the $r$-domination problem is solvable in polynomial time for trees and, more general, for bounded tree-width graphs.  
> **username_2**: @vble I guess $r$ is fixed. But why is the $r$-domination problem solvable for bounded tree width graphs? the power of such graphs have unbounded tree width.  
> **username_1**: Yes, $r$ is fixed, thanks. Yes, $G^r$ has unbounded tree-width but **bounded clique-width** (due to Gurski and Wanke) and the usual domination problem is MSO definable.  
> **username_0**: @vble Thanks! Can you provide references and make your comment an answer?  
> **username_1**: @ Nikhil: done.  

---

## 5 answers

### Answer by username_1 on 2013-11-07. Score: 15 | Accepted answer

An (optimal) $r$-domination for $G$ is an (optimal) domination for the $r$th power $G^r$ and vice versa
($G^r$ is obtained from $G$ by adding new edges between distinct vertices of distance at most $r$).

The following facts are well known: (1) All powers of a strongly chordal graph are strongly chordal
(A. Lubiw, Master thesis; see also Dahlhaus & Duchet, On strongly chordal graphs,
Ars Combin. 24 B (1987) 23-30), and (2) Domination is solvable in linear time for strongly chordal graphs
(M. Farber. Domination, independent domination and duality in strongly chordal graphs,
Discrete Appl. Math., 7 (1984) 115–130). Hence $r$-domination is solvable in polynomial time for
strongly chordal graphs, in particular for trees ($r$ fixed or not).

Gurski & Wanke proved in [this paper](http://www.sciencedirect.com/science/article/pii/S0166218X08004022)
that the clique-width of $G^r$ is at most $2\cdot (r+1)^{\text{tw}(G)+1}−2$, where $\text{tw}(G)$ is the tree-width
of $G$. Thus, for fixed $r$, the $r$th powers of bounded tree-width graphs have bounded clique-width.
Hence, for fixed $r$, $r$-domination is solvable in polynomial time for bounded tree-width graphs
(by Courcelle's theorem).


---

### Answer by username_3 on 2013-11-08. Score: 9

[Dawar and Kreutzer](http://arxiv.org/abs/0907.4283) have shown that the problem is fixed-parameter tractable on nowhere dense classes of graphs, which includes the planar graphs, the graphs of bounded (local) tree-width and all classes with (locally) excluded minors.

[Dvorak](http://arxiv.org/abs/1110.5190) has shown that there is a polynomial time constant factor approximation for classes of bounded expansion, which includes the planar graphs, graphs of bounded tree-width and all classes with excluded minors.


---

### Answer by username_4 on 2013-11-05. Score: 9

It is quite easy to do dynamic programming on graphs of treewidth $k$ for this problem.
One can keep for each vertex in a bag the shortest distance to some vertex in the partial solution and the distance to future solution needed to dominate the undominated vertices.

This in total gives a table size of $O(r^k)$ so for fixed $r$ this problem is FPT parameterized by treewidth, however if $r$ is not fixed this becomes an XP algorithm.
As far as I know the question of whether this problem is FPT for all values of $r$ is open.

> **Comments:**
> **username_5**: Maybe change $r^k$ to $r^{O(k)}$?  

---

### Answer by username_5 on 2017-03-29. Score: 5

There is a recent paper by Glencora Borradaile, Hung Le: [Optimal Dynamic Program for r-Domination Problems over Tree Decompositions](http://drops.dagstuhl.de/opus/volltexte/2017/6919/) (IPEC 2016). Here they show that there is an algorithm that given as input a graph $G$, an integer $r$, and a tree-decomposition of $G$ of width $w$, computes an optimal $r$-dominating set of $G$ in time $O((2r+1)^wn)$.
Furthermore, they show that this is the best one can do, in the following sense: an algorithm with running time $O((2r+1-\epsilon)^wn^{O(1)})$ for $\epsilon > 0$ would contradict the Strong Exponential Time Hypothesis.


---

### Answer by username_6 on 2017-03-30. Score: 2

A linear sequential algorithm to compute a optimal r-domination for a tree is due to Slater:

P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976.
doi:10.1145/321958.321964

A distributed algorithm for the same setting is due to Turau and Köhler:

Volker Turau and Sven Köhler. A Distributed Algorithm for Minimum Distance-k Domination in Trees. Journal of Graph Algorithms and Applications, 19(1):223–242,5 (see <http://jgaa.info/getPaper?id=354>)


---

