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?

  • $\begingroup$ 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$. $\endgroup$ – LetGBeTheGraph Feb 6 at 11:53
  • $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thank you very much, it really helped me. I wish you a nice weekend! $\endgroup$ – Razvan Tutuianu Feb 7 at 22:26

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.