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:Find a number $x \in \mathbb{N}: 0 < x < |V|$ $S := \{v \in V | dist(v) > x\}$ and $V \setminus S = \{v \in V | dist(v) < x\}$There is no edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network.$(S, V \setminus S)$ is a min-cut.Proof of correctness: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.This is a valid partition of $V$, as no node has label $x$.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 ...$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}$)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 networkAs 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?
Can I get all min-cuts after executing Push-Relabel?
max flow;max flow min cut