# Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

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. 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?

• 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 Nov 5 '13 at 18:53
• @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 Nov 6 '13 at 9:39
• 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 Nov 6 '13 at 12:03
• @vble Thanks! Can you provide references and make your comment an answer? – Nikhil Nov 7 '13 at 13:01
• @ Nikhil: done. – vb le Nov 7 '13 at 16:52

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 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).

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.

• Maybe change $r^k$ to $r^{O(k)}$? – daniello Apr 4 '17 at 11:20

Dawar and Kreutzer 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 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.

There is a recent paper by Glencora Borradaile, Hung Le: Optimal Dynamic Program for r-Domination Problems over Tree Decompositions (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.

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)