0
$\begingroup$

I'm looking for find the min-cut of a fully-connected directed graph (with cycles), or an undirected graph.

Karger's works but is not guaranteed to produce the correct solution. Is there a guaranteed algorithm?

I came across max-flow algorithms. Do these only work if the graph is acyclic?

Thanks.

$\endgroup$
2
$\begingroup$

Directed graphs: Use any max-flow algorithm together with the max-flow min-cut theorem. There are any number of algorithms for max-flow in an arbitrary directed graph. This is bog-standard stuff that should be covered in any algorithms textbook. See also minimum cut.

Undirected graphs: Use a min-cut algorithm for undirected graphs, e.g., Karger's algorithm or this lecture. I don't know what you mean by "it is not guaranteed to provide a solution"; the probability that it fails to find a solution is exponentially small, e.g., you can make this probability smaller than the chance that a cosmic ray hits your computer, makes it compute the wrong answer, and then you get struck by lightning and die anyway. Tough luck about that lightning, by the way.

Next time do more research before asking.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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