Let G = (V,E) be a unit-capacity graph with n vertices and m edges. Let T denote
ID: 650164 • Letter: L
Question
Let G = (V,E) be a unit-capacity graph with n vertices and m edges.
Let T denote all the spanning trees in G.
If we run Karger's algorithm, we will get a random spanning tree in T formed by the contracted edges, we denote this distribution of spanning trees by D1.
On the other hand, if we assign a random weight in (0,1) to each edge and compute a minimum spanning tree using Kruskal's algorithm, then another distribution D2 over T is obtained.
Show that the distributions D1 and D2 are identical.
I have no idea where to start. Any hint is helpful!
Explanation / Answer
You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random edge. Similarly, if you choose the weights at random, the first edge that is chosen in Kruskal's algorithm is a uniformly random edge.
What about the next edge? Karger's algorithm selects another uniformly random edge. After removing the first edge, the remaining edges are ordered completely at random. Hence the next edge chosen by Kruskal's algorithm is also uniformly at random.
From the third edge hence, some edge choices would be bad
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.