0
$\begingroup$

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?

$\endgroup$

closed as off-topic by Aaron Roth, Sasho Nikolov, Jeffε, David Eppstein, Kaveh Sep 16 '13 at 21:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Do you mean "this is different because nodes need NOT share an edge"? $\endgroup$ – user1694 Aug 23 '13 at 7:43
  • 1
    $\begingroup$ this is not a research level question. also, think about the star graph $\endgroup$ – Sasho Nikolov Aug 23 '13 at 21:57
  • 1
    $\begingroup$ Are you proposing an algorithm that ignores the edge set and merges vertices at random? $\endgroup$ – Aaron Roth Aug 24 '13 at 22:09
  • 1
    $\begingroup$ 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) $\endgroup$ – Sasho Nikolov Aug 25 '13 at 3:50
  • 3
    $\begingroup$ @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. $\endgroup$ – Aaron Roth Aug 25 '13 at 14:13
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (a) thanks. (b) Sorry, I wasn't totally clear in my question. I'm not really interested in run time. I was thinking that there might be a reason to contract edges and not nodes because you might affect probability that the algorithm returns a (global) min cut. $\endgroup$ – larry d johnson Aug 23 '13 at 16:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.