1
$\begingroup$

How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ?

I've seen it stated that one can apply a maximum flow algorithm to compute a minimum $s$-$t$ cut in an undirected graph. However, trying to adapt the Edmond-Karp algorithm this doesn't make much sense, or does it ?

I know a graph can be viewed as an undirected graph with $(u,v)$ and $(v,u)$ replacing $\{u,v\}$...

$\endgroup$
3
  • 1
    $\begingroup$ You can straightforwardly apply any flow algorithm for directed graphs to find the max flow in an undirected graph just by modifying the graph slightly. You seem to almost have answered your own question in the final sentence. $\endgroup$ May 25 '15 at 15:08
  • $\begingroup$ But how should the algorithm be adjusted, and how should capacities of new edges be ? $\endgroup$
    – Shuzheng
    May 25 '15 at 15:33
  • $\begingroup$ I think you don't event need to adjust the algorithm. Just for each undirected edge {u,v} with capacity c, create two edges (u,v) and (v,u), each having capacity c. Now run algorithm on the new graph and the result is the result for undirected graph. The amount of flow over edge {u,v} is ||flow(u,v)|-|flow(v,u)||. $\endgroup$ May 25 '15 at 21:06
2
$\begingroup$

You don't need to adapt the algorithm, any maximum flow algorithm for directed graphs works by replacing the edges with a forward and backward arc as you suggested. Denote this directed graph $D=(V,A)$. Take the capacities $C(u,v)=C(v,u)$ of both arcs equal to the original edge. Then, let $F(u,v)$ be the maximum flow returned by your algorithm on the directed graph.

To find the cut you need the (directed) residual graph $G_f$ which can be constructed explicitly from the flow by taking $D$ with capacities $C_f(u,v) = C(u,v) - F(u,v)$. Now find the set $S$ of vertices reachable in $G_f$ from $s$, where you can only cross arcs with positive capacity, and let its complement be $T=V\setminus S$. Then $(S, T)$ gives a minimum $s-t$ cut.

To see why this works, note that the capacities in the residual graph give the additional amount of flow in each direction that can be sent over an edge. That is, given the flow already in place, and if you assume that opposite flows cancel each other out. This means a saturated edge has 0 residual capacity in the direction of the flow and double its original capacity in the reverse direction (as $F(u,v)=-F(v,u)$).

Any vertex reachable from $s$ in $G_f$ can receive more flow. Since $F$ is a maximum flow, $t$ cannot be in $S$. Similarly any edge between $u \in S$ and $v \in T$ must be saturated with flow in that direction, otherwise $v$ would be reachable from $s$. Now suppose the capacity of the cut-set is larger than the $s-t$ flow, then the flow from $S$ to $T$ is larger than the flow from $S$ to $t$, which means there must be flow back from $T$ to $S$ which is a contradiction. Since any $s-t$ cut is at least as large as the maximum $s-t$ flow it follows $(S,T)$ is a minimum $s-t$ cut.

$\endgroup$

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.