# Can I get all min-cuts after executing Push-Relabel?

The push-relabel algorithm (here is push-relabel as pseudo-code) assigns a distance-label to each node.

After executing push relabel, you have those distance labels and a max flow in a given network $N = ((V, E), s, t, c)$ with $E \subseteq V \times V$, $s,t \in V$, $c:E\rightarrow \mathbb{R}_0^+$.

How to get one min-cut after executing push-relabel:

1. Find a number $x \in \mathbb{N}: 0 < x < |V|$
2. $S := \{v \in V | dist(v) > x\}$ and $V \setminus S = \{v \in V | dist(v) < x\}$
3. There is no edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network.
4. $(S, V \setminus S)$ is a min-cut.

Proof of correctness:

1. Such a number $x$ exists, because you have $|V|$ nodes that can have labels, $s$ has the label $|V|$, $t$ has the label $0$. So you have $|V|-1$ possible numbers for $x$ and only $|V|-2$ nodes that can have labels.
2. This is a valid partition of $V$, as no node has label $x$.
3. If there was an edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network it would have to be ...

1. $dist(u) \geq dist(v) + 2$ as we defined $S$ like this: \begin{align} & dist(u) > x \land x > dist(v) \\ \Rightarrow & dist(u) - 1 \geq x \land x \geq dist(v) + 1\\ \Rightarrow & dist(u) \geq dist(v) + 2 \end{align})
2. For every edge in the residual network you can say: $dist(u) \leq dist(v) +1$

$\Rightarrow 2 \leq 1 \Rightarrow$ Error $\Rightarrow$ there is no edge between $S$ and $V \setminus S$ in the residual network

4. As there is no free capacity in the residual network between the sets $S$ and $V \setminus S$, the value of the min cut is the max flow. According to max-flow min-cut theorem $(S, V \setminus S)$ is a min-cut.

So the given algorithm can find at least one min-cut quite fast after push-relabel was executed. As $x$ can have more values (the labels of some nodes might be the same and they can go up to $2|V|-1$ as far as I know), you can also find more than one min-cut.

My question:

Do I find all min-cuts this way?

-
I would be interested in such algorithm of enumerating all cuts too ! – alena May 5 '15 at 15:18