Question

I stumbled across this question and answer (source):

Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.

Answer: First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow.

Does this mean that the Ford-Fulkerson algorithm will reach max flow if given any valid flow as input, instead of initializing all edges to 0 at the start?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top