Directed Trees Question Help

Question

For part (a), I assume we build some version of a minimal spanning tree. Instead of the total sum of edges being minimum, the path from s to every vertex must be minimal. Is there a way to reduce this problem to the minimal spanning tree problem?

For part (b), we repeatedly build this required tree, until squaring the edges further doesn't change the tree that is built, right? I'm not sure what the question is asking: what does it mean to describe this characterization of the way of computing the length of paths?

For part (c), we build a stable tree as in part (b), and show that this is a minimum spanning tree, right?

Thanks for the help.

Answer 1

I'll tackle part (a)

I don't see the way how to reduce to MST. In fact I have an example,

Take a directed chain from $s$ with all edges of weight $1$ (I know the problem wants $>1$, but just multiply all weights by the same constant). Now the paths in this tree from $s$ to (let denote them) $v_{next}, v_0, v_1, v_2, \ldots, v_n$ are of weight $1, 2, \ldots, n+2$ respectively.

Now connect $s$ to $v_1, v_2, \ldots v_n$ by edges of weight $1, 2, \ldots, n$. In this graph the shortest paths to $v_1, v_2, \ldots v_n$ are those edges. Taking all those new edges and $(s,v_{next}), (v_{next}, v_0)$ produces a tree with weight almost $\frac{n}{2}$ higher than of MST.

I suggest the procedure to build the tree in question.

• Build the shortest path to each node $v$ in graph $G$, that starts in $s$.
• Take the union of all those paths, call it $G_1 = (V, \cup_{e\, \in\,\text{some shortest path}}~\{e\})$.
• For any vertex $v$ in $G_1$, drop all the incoming edges, except the lightest one.

I claim, what left is the desired tree.