2
$\begingroup$

Given an undirected graph $G=(V,E)$ could we build a tree $T$ that approximates the distances from given vertex $r$ and the total weight, i.e. $\forall x \in V, d_G(r,x) \le d_T(r,x) \le 3 \cdot d_G(r,x)$ and $w(T) \le 3\cdot w(\text{MST}(G))$, where $\text{MST}$ is the minimum spanning tree and $w(\cdot)$ is the weight function i.e. $w:\Bbb E \to \Bbb R^+$. $d_G(v,u)$ denotes the shortest path distance between $v$ and $u$ in $G$, and $d_T(v,u)$ is the shortest path distance between $v$ and $u$ in $T$.

Could any one help me to understand how to build this tree and if there is any material that would help?

$\endgroup$
  • 1
    $\begingroup$ @FayezAbdlrazaqDeab: how would one construct the minimum spanning tree that you need to compare to? Look up Prim's algorithm. $\endgroup$ – Wandering Logic Apr 27 '13 at 23:05
  • $\begingroup$ assume you build $T$ who much is it close to $MST$ ? or something like this ... I dont think you need to build it $\endgroup$ – Fayez Abdlrazaq Deab Apr 27 '13 at 23:12
  • 1
    $\begingroup$ @FayezAbdlrazaqDeab, as wandering logic mentioned, seems shortest path tree is 2 approximation, you can think about this and update your question with your thought. $\endgroup$ – user742 Apr 27 '13 at 23:18
  • $\begingroup$ this give us a perfect distances but how much it approximates the mst weight? it dosnt fulfill it! take a circle all weights are 1 and just one of them is n-2 $\endgroup$ – Fayez Abdlrazaq Deab Apr 27 '13 at 23:25
  • 1
    $\begingroup$ In the circle you mentioned all of your inequalities are correct. p.s: with same argument you can prove is 2-approximation. $\endgroup$ – user742 Apr 27 '13 at 23:40
3
$\begingroup$

Your problem is solved in the following paper by Khuller, Raghavachari, and Young. They show that you can construct a tree in which distances from the root are stretched by at most $\alpha$ and the total weight of the tree is at most $1 + 2/(\alpha - 1)$ times the weight of the MST. So, with $\alpha=3$, you can get $2$ times the weight of the MST. The algorithm does a depth-first traversal of the MST, and adds paths from the shortest path tree when necessary, roughly speaking maintaining a shortest path structure in the current graph, which consists of the MST edges and the edges added from the shortest path three. Check the paper for details.

As I mentioned in the comment, there are graphs in which the weight of the shortest path tree rooted at some vertex is greater than the MST weight by $\Omega(n)$. One example is a path of unit weight edges, and edges from the first vertex in the path to the $i$-th vertex of weight just slightly less than $i-1$.

$\endgroup$

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.