1
$\begingroup$

Suppose I'm given an undirected graph and two nodes: v and u.

If I understand Karger's algorithm correctly, it's used to find a minimum cut of a graph, not the ("the" because there is only one for any given graph) minimum cut such that v is in one part of graph and u is in the other part.

Why don't we simply find the vertex with the minimum number of edges and remove those edges. Thus, we "partition" the graph into two subgraphs: the node which had the minimum number of edges and the rest of the original graph. What am I missing?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ We prefer that you ask only one question per post. If you have multiple questions, you can post each one separately. That helps keep track of which ones have been answered and which ones haven't. Feel free to edit your question to remove the first question and post it separately. $\endgroup$
    – D.W. ♦
    Jan 23, 2017 at 2:32

1 Answer 1

Reset to default
5
$\begingroup$

Even in an unweighted graph, your suggested algorithm doesn't work: take a graph of 6 vertices with triangle a, b, c, and triangle d, e, f, with an edge between c and d. Vertices a, b, e, and f each have minimal degrees of 2, but cutting the graph between the two triangles gives a cut of 1.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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