Set Covering Problem for Weighted Graph

Question

I am looking for solution of the following problem.

Let $G$ be a weighted graph with (positive) weights. The length of a path in a weighted graph is the sum of the weights of the selected edges. The distance between two nodes is a minimal length of path between these nodes. If $N$ is a node in $G$ and $R > O$, we can define a circle with center at $N$ and radius $R$, or $N,R$-circle, as a set of all nodes in $G$, whose distance to node $N$ is $\leq R$; we say that all these nodes are covered by this $N,R$-circle.

Question: what is a minimum number of circles of radius $R$ that cover all nodes of the graph $G$.

In my case $G$ is a tree with a finite number of nodes and edges, may be it simplifies the problem?

Thank you.

Answer 1

I have two news for you: a good one and a bad one. The good one is that your problem is equivalent to a well-known problem, so there is no need to “re-invent a wheel”. To see that, consider new graph $G’$ with the same set of vertices as $G$, but vertices $u$ and $v$ of $G’$ are adjoined by an edge iff the distance between $u$ and $v$ in $G$ is at most $R$. Then your problem is equivalent to find a smallest dominating set of vertices in the graph $G’$. But the bad news is that this problem is NP-hard, so it should admit (known) efficient algorithms only in special cases.

Answer 2

I have two ideas for this problem.

First, your problem seems to be related to the p-center problem on trees. In the p-center problem one looks for $p$ nodes $X$ in the tree such that the maximal distance between an arbitrary node and a node from $X$ is minimized. This distance is what you defined as radius. So in your problem the radius is fixed and you want to minimize the number of chosen nodes, while in the p-center problem, the number of nodes is fixed and the radius is minimized. As a reference for the p-center problem on trees you might have a look at this paper from 1983 by Megiddo and Tamir.

My second idea is an algorithm. Assume that the tree is rooted at $v_0$. Then node $v$ is above node $u$ if $v$ is closer to $v_0$ than $u$. The idea of he algorithm is to start covering the tree from the leafes. An uncovered leaf will be covered a node as high in the tree as possible.

1.  While the graph is not yet covered
2.      Find an uncovered leaf u'.
3.      u = u'
4.      Let v be the node above u (i.e. the unique neighbor of u).
5.      If dist(u',v) > R
6.          Choose u as center.
7.          Remove all nodes covered by u from the graph.
8.          Apply this procedure for all remaining subgraphs.
9.      Else
10.         If the  dist(v,w) <= R for each node w below v
11.             u = v and continue at step 4.
12.         Else
13.             Pick a node w below v such that dist(v,w) > R.
14.             u' = w and continue at step 3.
15.         End If
16.     End If
16. End While