1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! Is that including 'constructing' the residual graph or do we take for granted that a residual graph is 'kept' beforehand? $\endgroup$ – Nyfiken Gul Feb 13 '17 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$ – Yuval Filmus Feb 13 '17 at 18:51

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.