I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow $f_e$ is the maximum flow of the flow graph $G$ in $O(|E|)$ time complexity.

I've thought about running one iteration of Ford-Fulkerson to see if there is an augmenting path from the source $s$ to the sink $t$, but couldn't such a solution get a time complexity worse than $O(|E|)$ in the worst case?


1 Answer 1


A flow is maximum if there is no $s$-$t$ path in the residual network. You can check this in time $O(|E|)$.

  • $\begingroup$ Thank you! Is that including 'constructing' the residual graph or do we take for granted that a residual graph is 'kept' beforehand? $\endgroup$ Feb 13, 2017 at 17:02
  • 1
    $\begingroup$ You haven't specified how instances to your problem look like, but the most reasonable choice is a flow network and a flow. Everything else has to be computed. $\endgroup$ Feb 13, 2017 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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