7.1 Maximum Flow and Ford Fulkerson

The problem is to find a set of flows along directed edges with a capacity constraint that maximizes flow between two nodes. Assume integer capacities, no edges entering source or leaving sink, and connected. The sum of flows out of a node must equal the sum of flows in; since all flow must pass somewhere, any cut separating the source and sink bounds the capacity above. Cannot use any obvious greedy algorithm, as a misdirected flow can cut off future paths. Thus we use a form of backtracking; create a residual graph that includes reverse edges for those that have flows (corresponding to the ability to decrease that flow) and add flow in that graph (updating it each time) until there is no augmenting path. Since capacity is finite and each iteration increases capacity, this process terminates, with no more than C loops (the capacity of the cut between the source and the rest of the graph) each taking m time (time proportional to length of the augmenting path), giving O(Cm).

Why can we not use the true capacity, since it is well-defined for a graph? I understand that it is not conveniently computable, but it is a constant.

No insights.

No complaints.