<p>The problem is solved in the paper <em>P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976.</em> It considers an even more general problem using dynamic programming.</p>

CC BY-SA 3.0
2014-01-26T14:18:33.147Z
2014-01-26T14:18:33.147Z
Volker Turau
<p>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}$?  </p>

CC BY-SA 3.0
2014-01-26T04:18:32.150Z
This looks like a standard (if somewhat advanced) dynamic programming problem, at least if all the edge-weights are non-negative.
Jeffε
CC BY-SA 3.0
2014-01-26T05:37:39.930Z
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.
Hung Le
CC BY-SA 3.0
2014-01-26T05:46:27.107Z
O(r) and O(1) I mean for each node of the tree.
Hung Le
CC BY-SA 3.0
2014-01-26T16:08:52.403Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T20:19:35.770Z
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.
Jeffε
<graph-algorithms><tree>
minimum distance r-dominating set on tree
Hung Le
# minimum distance r-dominating set on tree

(Asked by: username_0 on 2014-01-26)

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}$?

**Tags:** graph-algorithms, tree
> **Comments:**
> **username_1**: This looks like a standard (if somewhat advanced) dynamic programming problem, at least if all the edge-weights are non-negative.  
> **username_0**: 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.  
> **username_0**: O(r) and O(1) I mean for each node of the tree.  
> **username_2**: @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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-01-26. Score: 4

The problem is solved in the paper *P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976.* It considers an even more general problem using dynamic programming.


---

