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

<p>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). </p>

<p>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.</p>

CC BY-SA 3.0
2013-02-15T15:53:36.633Z
2013-02-15T15:53:36.633Z
Jaime Cohen
<p>The <a href="http://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm">push-relabel algorithm</a> (here is <a href="https://github.com/MartinThoma/LaTeX-examples/raw/master/source-code/Pseudocode/Goldberg-Tarjan-Push-Relabel/Goldberg-Tarjan-Push-Relabel.pdf">push-relabel as pseudo-code</a>) assigns a distance-label to each node. </p>

<p>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^+$. </p>

<p><strong>How to get one min-cut after executing push-relabel:</strong></p>

<ol>
<li>Find a number $x \in \mathbb{N}: 0 &lt; x &lt; |V|$ </li>
<li>$S := \{v \in V | dist(v) &gt; x\}$ and $V \setminus S = \{v \in V | dist(v) &lt; x\}$</li>
<li>There is no edge $(u,v)$ with $u \in S, v \in V \setminus S$ in the residual network.</li>
<li>$(S, V \setminus S)$ is a min-cut.</li>
</ol>

<p><strong>Proof of correctness:</strong></p>

<ol>
<li>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.</li>
<li>This is a valid partition of $V$, as no node has label $x$.</li>
<li><p>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 ...</p>

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

<p>$\Rightarrow 2 \leq 1 \Rightarrow $ Error $\Rightarrow$ there is no edge between $S$ and $V \setminus S$ in the residual network</p></li>
<li>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 <a href="http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem">max-flow min-cut theorem</a> $(S, V \setminus S)$ is a min-cut.</li>
</ol>

<p>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.</p>

<p><strong>My question</strong>: </p>

<p>Do I find all min-cuts this way?</p>

CC BY-SA 3.0
2015-05-05T15:18:18.830Z
I would be interested in such algorithm of enumerating all cuts too !
alena
CC BY-SA 4.0
2020-09-29T19:02:03.473Z
Can you elaborate on the complexity of that algorithm?
Roy
CC BY-SA 4.0
2020-09-30T14:59:01.460Z
Please edit the post to clarify what you mean by "Do I find all min-cuts this way?".  Are you asking whether, for any flow network, and any min-cut (S, T) in the flow network, there is some execution of the algorithm that finds (S, T) in this way?  Or, say, whether after a single execution of the algorithm, every min cut (S, T) can be found this way (for some x)?
Neal Young
<max-flow><max-flow-min-cut>
Can I get all min-cuts after executing Push-Relabel?
Martin Thoma
# Can I get all min-cuts after executing Push-Relabel?

(Asked by: username_0 on 2013-02-14)

The [push-relabel algorithm](http://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm) (here is [push-relabel as pseudo-code](https://github.com/MartinThoma/LaTeX-examples/raw/master/source-code/Pseudocode/Goldberg-Tarjan-Push-Relabel/Goldberg-Tarjan-Push-Relabel.pdf)) 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](http://en.wikipedia.org/wiki/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?

**Tags:** max-flow, max-flow-min-cut

> **Comments:**
> **username_1**: I would be interested in such algorithm of enumerating all cuts too !  
> **username_2**: Can you elaborate on the complexity of that algorithm?  
> **username_3**: Please edit the post to clarify what you mean by "Do I find all min-cuts this way?".  Are you asking whether, for any flow network, and any min-cut (S, T) in the flow network, there is some execution of the algorithm that finds (S, T) in this way?  Or, say, whether after a single execution of the algorithm, every min cut (S, T) can be found this way (for some x)?  

---

## 1 answers

### Answer by username_4 on 2013-02-15. Score: 5

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.


---

