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?

Improve this question
$\endgroup$
5
  • 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
    Commented Nov 5, 2013 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
    Commented Nov 6, 2013 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
    Commented Nov 6, 2013 at 12:03
  • $\begingroup$ @vble Thanks! Can you provide references and make your comment an answer? $\endgroup$
    – Nikhil
    Commented Nov 7, 2013 at 13:01
  • $\begingroup$ @ Nikhil: done. $\endgroup$
    – vb le
    Commented Nov 7, 2013 at 16:52

5 Answers 5

Reset to default
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).

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Maybe change $r^k$ to $r^{O(k)}$? $\endgroup$
    – daniello
    Commented Apr 4, 2017 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.

Improve this answer
$\endgroup$
5
$\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.

Improve this answer
$\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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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