<p>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. </p>

CC BY-SA 3.0
2013-08-23T16:24:34.227Z
(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.
larry d johnson
CC BY-SA 3.0
2013-08-23T13:26:43.840Z
2013-08-24T21:19:21.073Z
2013-08-24T21:19:21.073Z
Rasto S.
<p>Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge).</p>

<p>Is there a reason why this is so?</p>

CC BY-SA 3.0
2013-08-23T16:21:48.793Z
here is what I mean: if you contract nodes, not edges, then you can merge nodes that do not share an edge. It seems to me that if restrict yourself to nodes that share an edge, then it is equivalent to contracting edges.
larry d johnson
CC BY-SA 3.0
2013-08-23T21:57:39.783Z
this is not a research level question. also, think about the star graph
Sasho Nikolov
CC BY-SA 3.0
2013-08-24T22:09:42.120Z
Are you proposing an algorithm that ignores the edge set and merges vertices at random?
Aaron Roth
CC BY-SA 3.0
2013-08-25T03:14:50.147Z
@AaronRoth yes. How would that effect analysis?
larry d johnson
CC BY-SA 3.0
2013-08-25T03:15:18.977Z
I've thought about the star graph, and I'm not sure how that is relevant.
larry d johnson
CC BY-SA 3.0
2013-08-25T03:50:36.830Z
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)
Sasho Nikolov
CC BY-SA 3.0
2013-08-25T14:13:04.817Z
@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.
Aaron Roth
<randomized-algorithms><max-flow-min-cut>
karger's algorithm contracting nodes not edges
larry d johnson
# karger's algorithm contracting nodes not edges

(Asked by: username_0 on 2013-08-23)

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?

**Tags:** randomized-algorithms, max-flow-min-cut

> **Comments:**
> **username_0**: here is what I mean: if you contract nodes, not edges, then you can merge nodes that do not share an edge. It seems to me that if restrict yourself to nodes that share an edge, then it is equivalent to contracting edges.  
> **username_1**: this is not a research level question. also, think about the star graph  
> **username_2**: Are you proposing an algorithm that ignores the edge set and merges vertices at random?  
> **username_0**: @AaronRoth yes. How would that effect analysis?  
> **username_0**: I've thought about the star graph, and I'm not sure how that is relevant.  
> **username_1**: 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)  
> **username_2**: @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.  

---

## 1 answers

### Answer by username_3 on 2013-08-23. Score: 1

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.

> **Comments:**
> **username_0**: (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.  

---

