<p>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. <a href="https://www.sciencedirect.com/science/article/pii/S0196677499910398" rel="noreferrer">https://www.sciencedirect.com/science/article/pii/S0196677499910398</a></p>

<p>More interesting and difficult case is $\alpha$-approximation mincuts for $\alpha &gt; 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. <a href="https://dl.acm.org/citation.cfm?id=365415" rel="noreferrer">https://dl.acm.org/citation.cfm?id=365415</a></p>

CC BY-SA 4.0
2018-05-06T19:47:06.707Z
2018-05-06T19:47:06.707Z
Chandra Chekuri
<p>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</p>

<p><a href="https://cstheory.stackexchange.com/questions/9399/counting-the-number-of-distinct-s-t-cuts-in-a-oriented-graph/9400">Counting the number of distinct s-t cuts in a oriented graph</a></p>

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

<reference-request><graph-algorithms><counting-complexity>
What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?
srey
# What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?

(Asked by: username_0 on 2018-05-06)

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](https://cstheory.stackexchange.com/questions/9399/counting-the-number-of-distinct-s-t-cuts-in-a-oriented-graph/9400)

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

**Tags:** reference-request, graph-algorithms, counting-complexity

---

## 1 answers

### Answer by username_1 on 2018-05-06. Score: 4 | Accepted answer

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>


---

