Problem Detail: 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!
Asked By : MMP
Answered By : Yuval Filmus
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 – will close a cycle. However, by design it doesn’t happen in both algorithms, and otherwise the chosen edge is uniformly random. This is the idea of the proof, and it remains to make it formal. That’s your task.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33410
