1
$\begingroup$

Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$.

Also, we are given a max flow function $f$ on that network.

Let $R_f$ be the residual network of $f$.

I would like to prove that the set formed by all the nodes reachable from $s$ in $R_f$ is a subset of $S$ from any min-cut $(S,T)$.

I tried to write a proof by contradiction but I'm just getting stuck every time trying to analyze the Min-Cut after removing a certain node.

$\endgroup$
1
  • $\begingroup$ Hint, for a path starting at $s$ to reach a node in $T$, it must cross the cut. $\endgroup$
    – John L.
    Feb 14 at 19:52

1 Answer 1

1
$\begingroup$

The key idea is to understand max-flow min-cut theorem and its proof. The following observation is a corollary of that theorem basically.

Lemma. Let $f$ be a max-flow and $\mathcal C=(S, T)$ be a min-$(s,t)$-cut. Then

  • for any edge $(u,v)$ such that $u\in S$ and $v\in T$, $f((u,v))=c((u,v))$.
  • for any edge $(u,v)$ such that $u\in T$ and $v\in S$, $f((u,v))=0$.

In plain words, the lemma says that $f$ must use all capacities of all edges crossing $\mathcal C$ without using any capacities of any edge going the other way.

Proof. The conservation of flows implies that $|f|=f_{out}(S)-f_{in}(S)$. Since $f_{out}(S)\le c(\mathcal C)=|f|$, where $c(\mathcal C)$ is the capacity of $\mathcal C$ and $f_{in}(S) \ge0$, we must have $f_{out}(S)= c(\mathcal C)$ and $f_{in}(S)=0$. $\checkmark$


The lemma above means that given any min-cut $(S, T)$, in the residual network $R_f$, no edge of positive capacity goes from $S$ to $T$ since

  • the capacity of any edge that goes from $S$ to $T$ is reduced to $0$ in $R_f$, and
  • the "pushed-back capacity" of any edge that goes from $T$ to $S$ is $0$ since $f$ is 0 on those edges.

In other words, any path of edges of positive capacity in $R_f$ cannot cross the cut $(S,T)$. So, any path of edges of positive capacity that starts from $s$, which is a node in $S$, must stay in $S$. $\checkmark$


Exercise (every maximal flow yields the same minimal cut) Given a flow network $(G,s,t,c)$ and a flow $f$, let $S_f$ be the set of all vertices that are reachable from $s$ in the residual network of $f$. Given two maximal flows $f_1$ and $f_2$, show that $S_{f_1}=S_{f_2}$.

$\endgroup$
2
  • $\begingroup$ thank you for the answer and the edit! the proof approach is much more clear to me now. $\endgroup$
    – Riem
    Feb 15 at 7:13
  • $\begingroup$ You are welcome. $\endgroup$
    – John L.
    Feb 15 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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