2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Stackexchange. You'll find that simple "Here's the statement of my exercise, solve it for me" posts will be poorly received. It is better to add context: to say what you understand about the problem, what you've tried so far, etc. Something to both show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$ – Frentos Jan 18 '16 at 0:02
  • $\begingroup$ Are you looking for some asymptotics, or an algorithm, and are the weights integer valued? $\endgroup$ – David Kleiman Jan 18 '16 at 0:18
  • $\begingroup$ I am looking for algorithm. If no exact solution, heuristics will be good. I just would like to know if this problem is known and solved in order not to "re-invent a wheel". Otherwise, I will come up with some heuristics myself. $\endgroup$ – user308569 Jan 18 '16 at 5:43
  • $\begingroup$ The weights are not integer, but we can "re-calibrate" the problem and with some approximation assume that the weights are integer. $\endgroup$ – user308569 Jan 18 '16 at 5:44
1
$\begingroup$

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 
$\endgroup$
  • $\begingroup$ Thank you all for very useful information. $\endgroup$ – user308569 Jan 19 '16 at 20:15
  • $\begingroup$ philipph, thank you for the link to the paper from 1983 by Megiddo and Tamir and for the algorithm. My original problem (for a given r>0 to locate a minimum number of centers M(r) so that every point is within a distance r from at least one center) is inverse to continuous p-center problem and considered in the paper by Chandrasekaran and Daughety (referenced as [2] in the paper you provided a link for). Do you have a copy of this paper? Is your algorithm the same as proposed in [2]? Are steps 3 and 4 in your algorithm related to the lines of the pseudo-code numbers on the left side? $\endgroup$ – user308569 Jan 20 '16 at 14:36
  • $\begingroup$ Just found the paper by Chandrasekaran and Daughety here: kellogg.northwestern.edu/research/math/papers/357.pdf $\endgroup$ – user308569 Jan 20 '16 at 14:51
  • $\begingroup$ @user308569 Yes, by steps 3 and 4 I refer to the line numbers of the algorithm. I think my algorithm is essentially the same as in the paper. however, I missed some special cases. You'd better go with the algorithm from the paper by Chandrasekaran and Daughety. $\endgroup$ – philipph Jan 21 '16 at 8:44
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This reduction does not show that the problem at hand is NP-hard. To prove NP-hardness you would need to reduce an NP-hard problem to the problem at hand. $\endgroup$ – philipph Jan 19 '16 at 11:22
  • $\begingroup$ @philipph You can do so by letting an arbitrary graph have all edges weighted 1 and then ask for the minimum number of circles of radius 1.5. This will give you a minimum dominating set. $\endgroup$ – Sean English Jan 19 '16 at 11:25
  • $\begingroup$ @SeanEnglish That is correct. So in general graphs the problem is NP-hard. For trees, however, the minimum dominating set problem is not NP-hard. I guess that the problem given here is not NP-hard. $\endgroup$ – philipph Jan 19 '16 at 11:53
  • $\begingroup$ Oh yes, sorry I did not see that the asker was interested in only trees. In that case, I would guess same as you. $\endgroup$ – Sean English Jan 19 '16 at 11:57

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.