# minimum distance r-dominating set on tree

Given a graph G = (V,E) with edge and vertex weights. The minimum distance r-dominating set problem for a graph G = (V,E) requires to find a set S $\in$ V of smallest vertex-weight such that every vertex v not in S, there is a vertex u in S such that d(u,v) $\leq$ r. Distance is defined by the length of shortest path on graph. Does anyone know papers that solve this problem on a $\textbf{tree}$?

• This looks like a standard (if somewhat advanced) dynamic programming problem, at least if all the edge-weights are non-negative. Jan 26, 2014 at 4:18
• Yes! JeffE. This problem could be solved by using dynamic programming. It takes O(r^2.|V|) with memory O(r). But I just want to check whether my algorithm is optimal or not. I found a paper that do better than my algorithm, O(1) memory with the same running time, but for trees with only edge weights. Jan 26, 2014 at 5:37
• O(r) and O(1) I mean for each node of the tree. Jan 26, 2014 at 5:46
• @Hunglv you should include such knowledge and the more precise "I am looking for lower bounds" as part of your question, so that we can better answer it and don't accidentally close it. Jan 26, 2014 at 16:08
• There's probably a four-russians optimization that improves the running time by some polyloglog factor. (At a high level: Precompute the answer to all subproblems of size $O(\log\log n)$, and then use the results of that precomputation as base cases in the dynamic programming algorithm.) If you're really looking for a proof that no polynomial improvement is possible, the correct answer is almost certainly "nobody knows". We really have no idea how to prove superlinear lower bounds for anything. Jan 26, 2014 at 20:19