1
$\begingroup$

Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5,

The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is $\text{Capacity}(S) = |L_2|+|R_1|+\text{edges}(L_1, R_2)$.

Here, $L_1 = S \cap L$, $L_2 = L \setminus S$, $R_1 = S \cap R$ and $R_2 = R \setminus S$. Furthermore, $L$ are the left edges and $R$ are the right edges.

I don't understand how he arrived at the conclusion that

number of edges that go from $S$ to $\overline{S} = |L_2|+|R_1|+\text{edges}(L_1, R_2)$

I don't understand the meaning of this expression. I drew it out on paper (highlighting all graph elements of the expression) and I still don't get it. Could somebody please explain to me how this expression is generated in simple and detailed terms?

$\endgroup$
  • $\begingroup$ What attempts have you made on your own? Have you tried working through some examples (with small graphs and cuts)? $\endgroup$ – D.W. Apr 18 '14 at 0:21
3
$\begingroup$

The flow network $G'$ is constructed from the original bipartite graph $G=(L,R,E)$ by adding two new nodes $s,t$, connecting $s$ to all nodes in $L$, connecting all nodes in $R$ to $t$, and orienting all edges in $E$ from $L$ to $R$. And $s$-$t$ cut in $G'$ has the form $(S,\overline{S})$ where $s \in S$, $t \in \overline{S}$. The edges crossing the cut are:

  1. Edges from $s$ to $\overline{S}$, that is, from $s$ to $\overline{S} \cap L$. There are $|L_2|$ of these.

  2. Edges from $S$ to $t$, that is, from $S \cap R$ to $t$. There are $|R_1|$ of these.

  3. Edges from $S \setminus \{s\}$ to $\overline{S} \setminus \{t\}$, that is, from $S \cap L$ to $\overline{S} \cap R$. There are $\mathrm{edges}(L_1,R_2)$ of these.

It is crucial that in $G'$ the edges are oriented, and that when counting edges crossing the cut $(S,\overline{S})$, we only count edges going from $S$ to $\overline{S}$.

$\endgroup$
  • $\begingroup$ Thanks for the clear answer. It makes sense to me now because there are no edges going back to s in this directed/oriented network and you just decompose each layer for the s-t cut (from s to L, from L to R and from R to t). $\endgroup$ – Wuschelbeutel Kartoffelhuhn Apr 16 '14 at 15:49

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.