# Algorithm for max flow and min cut, simultaneous

Good morning everyone. I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems was asking for an algorithm. The problem is:

Let $$R = (G,S,T,c)$$ be a network, $$x$$ is a flow in $$R$$ and $$(S,T)$$ a cut in $$R$$. Write an algorithm of complexity $$\mathcal O(n+m)$$ which will decide if $$x$$ is a maximum flow and $$(S,T)$$ a min cut, simultaneous.

Here I tried to use Ford Fulkerson with a queue, but I think my problem was on the queue. I didn't know how to include the min cut in the Ford Fulkerson Algorithm.

What is the right algorithm for this?

• Are you really supposed to construct the flow, which Ford-Fulkerson does? Or only decide if a given flow in a given network (with a given cut) is maximal? You know that a flow (or rather, its value) is maximal if and only if the capacity of the corresponding cut is minimal. You already know the cut. The $O(n+m)$ suggests iterating through the adjacency list of $G$ and using $x$ in some way. I assume that $n$ is the number of vertices, and $m$ is the number of edges, of $G$. – LetGBeTheGraph Feb 6 at 11:53
• It's not a must to construct the flow, I mean it is not asked for. And yes, n is the number of vertices, m the number of edges. I think that the problem asks for an algorithm to decide if a given flow is maximal etc. It's pretty bad formulated, I know. – Razvan Tutuianu Feb 7 at 22:24

1. Find the set of vertices $$A$$ $$=\{u$$: net flow out of $$u$$ is positive $$\}$$, and for each vertex $$u \in A$$ let $$y(u)$$ be the net flow out of $$u$$. To calculate the net flow of a vertex $$u$$, calculate the flow out of $$u$$ given by $$\sum x(u,v); v \in N_G(u)$$, and subtract from that the flow into $$u$$ given by $$\sum x(v,u); v \in N_G(u)$$.
2. Then $$(S,T)$$ is a minimum cut iff $$\sum_{u \in A} y(u) = \sum_{e \in (S,t)} c(e)$$, where $$c(e)$$ denotes the capacity of $$e$$.