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

Question

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?

Answer 1

I assume that your question is "Do I find all min s-t-cuts this way?"

I believe the answer is no. Note that there may be an exponential number of minimum s-t-cuts (connect vertex s to vertices {1,2,3, ...,n} and then each of these are connected to vertex t -- then there are 2^n min-s-t-cuts).

The way that I know for sure to enumerate all min-s-t-cuts is to recursively enumerate all directed cuts in the residual graph after the contraction of all strongly connected components. This algorithm can produce each cut in linear time per cut. If you need a detailed description of the enumeration algorithm I can provide to you the pseudocode.