14
$\begingroup$

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?

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

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

$\endgroup$
9
$\begingroup$

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.

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

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.