Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Finding a tree that approximates the distances and total weights

, ,
Problem Detail:

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?

#### Answered By : Sasho Nikolov

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$.