6
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I would be interested in such algorithm of enumerating all cuts too ! $\endgroup$
    – alena
    May 5 '15 at 15:18
  • $\begingroup$ Can you elaborate on the complexity of that algorithm? $\endgroup$
    – Roy
    Sep 29 '20 at 19:02
  • $\begingroup$ 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)? $\endgroup$
    – Neal Young
    Sep 30 '20 at 14:59
5
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.