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

  • 1
    $\begingroup$ This looks like a standard (if somewhat advanced) dynamic programming problem, at least if all the edge-weights are non-negative. $\endgroup$ – Jeffε Jan 26 '14 at 4:18
  • $\begingroup$ 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. $\endgroup$ – Hung Le Jan 26 '14 at 5:37
  • $\begingroup$ O(r) and O(1) I mean for each node of the tree. $\endgroup$ – Hung Le Jan 26 '14 at 5:46
  • 2
    $\begingroup$ @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. $\endgroup$ – Artem Kaznatcheev Jan 26 '14 at 16:08
  • $\begingroup$ 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. $\endgroup$ – Jeffε Jan 26 '14 at 20:19

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.


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.