Lightest Paths Tree that is 10 times heavier than an MST of the same graph

Question

Something I was asked to solve and tried to come up with a formula or some method to solve it after I did and couldn't.

• Given is a graph G=(V,E) that is undirected and weighted. Say we want to find the lightest paths tree (assume using Dijkstra's algorithm), we will call it K, and the Minimal Spanning Tree (assume using Kruskal's or Prim's algorithm) that we will call T. How can we ensure that the total weight of K is 10 times that of T if we run the algorithm on the same source node 's'? Important note: we cannot use negative weights on the edges.

The only way I managed to do this is by drawing and testing a bunch of graphs until I found something that works. It seems if we build a "ferris wheel" graph, and make the inside edges heavy and the outer edges light, we can manage getting a 10 times heavier lightest paths tree.

This definition of a "ferris wheel" graph is not formal - a node that is surrounded by more nodes and each node has an edge to the 'middle' node, and each surrounding node has an edge to the node next to it, forming something that resembles a ferris wheel)

Answer 1

Consider a graph $G = (V, E, w)$ such that:

• $V = \{s\}\cup \{v_1, …, v_n\}$;
• $E = E_1 \cup E_2$, with:
  • $E_1 = \{\{s, v_i\}\mid i\in \{1, …, n\}\}$, $f(s, v_i) = n + 1$
  • $E_2 = \{\{v_i, v_{i+1}\}\mid i \in \{1, …, n\}\}$, $f(v_i, v_{i+1}) = 1$ (with the convention that $v_{n+1} = v_1$).

Then the shortest path tree from $s$ will be $(V, E_1)$, of weight $n(n+1)$, and a MST will be all edges from $E_2$ but one, and one edge from $E_1$, of weight $(n-1) + n + 1 = 2n$. That means that there is a factor $\frac{n+1}2$ between the weight of the SPT and the MST. If you choose $n = 19$, you will get what you want.

You can repeat the process by adding other "layers" to the graph, with heavy radial edges and light transversal edges.

I don't know if that was what you described as a ferris wheel, but hey, at least I added a formal definition. (Then again, what you are asking is unclear)