# karger's algorithm contracting nodes not edges [closed]

Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge).

Is there a reason why this is so?

• Do you mean "this is different because nodes need NOT share an edge"?
– user1694
Aug 23 '13 at 7:43
• this is not a research level question. also, think about the star graph Aug 23 '13 at 21:57
• Are you proposing an algorithm that ignores the edge set and merges vertices at random? Aug 24 '13 at 22:09
• actually nevermind the star graph: you are making every cut equally likely (by a symmetry argument), there are $2^n$ cuts, and there are graphs where the min cut is unique (like a lollipop graph) Aug 25 '13 at 3:50
• @larrydjohnson as Sasho says, your proposed algorithm just ignores the input and outputs a uniformly random cut. Its easy to see that a uniformly random cut is not generally small -- indeed, its not a bad approximation to the -max- cut, since it cuts in expectation half of the edges in the graph. Aug 25 '13 at 14:13

The run-time of Karger-Stein is usually represented as a function of the number of vertices $n$, not of the number of edges. Therefore, placing an edge of weight $0$ between two vertices that previously did not share an edge would make your algorithm identical to theirs and not change the run-time.