I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of

Counting the number of distinct s-t cuts in a oriented graph

It says that due to this consequnce, the cuts of an unweighted graph can be listed in polynomial time, but the claim is unreferenced.


1 Answer 1


If you want exact minimum cuts then one can construct a cactus representation of the minimum cuts deterministically in polynomial time and use that to enumerate all minimum cuts. See below for a reference. https://www.sciencedirect.com/science/article/pii/S0196677499910398

More interesting and difficult case is $\alpha$-approximation mincuts for $\alpha > 1$. One can use Karger's randomized algorithm for this purpose. Simply run it sufficiently many time. However, if you want a deterministic algorithm, one can do it via tree packings. See Thorup's paper on k-cuts. https://dl.acm.org/citation.cfm?id=365415


Your Answer

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

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