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.

If we take a cut separating the source and sink, the total flow equals the flow across the cut minus the backflow across it. Thus the capacity of a cut bounds the capacity of the graph. More powerfully, the maximum flow equals the capacity for some cut (the minimum cut) (if all cuts are under capacity, there must be an augmenting path). Since the FFA terminates at this point, it returns a maximal flow. Moreover, this means that for any graph with integer capacities, there is an integer-valued flow (not necessarily unique, and not all maximal flows need have this property). The requirement of rational capacities is necessary as for some choices of augmenting paths, FFA on real capacities can run infinitely.

No questions.

No insights.

I would have liked to see an explanation of why rational numbers are permissible (which is, I believe, because in any finite graph with rational capacities there is a lcm of the capacities, and if all capacities are multiplied by that we get an integer graph). In any event, unless I miss something they say that the requirement that the flows be integers is necessary, state the problems with irrational capacities, and then state that real problems might have rational capacities, without showing that the rational capacities are workable.

The FFA can be used to solve bipartite matching, finding the greatest subset of a bipartite graph such that each node has at most one incident edge. Make all edges directed with unit capacity (in uniform direction) and add a source and sink, with unit capacity edges into the nodes chosen as the origin of the edges between the original nodes, and unit capacity edges from the destination nodes to the sink. The subset of the original edges with positive flow in a valid flow through this graph are a valid matching of the original graph, since each origin node only has one unit of incoming flow to distribute and each destination node can only handle one unit of flow. Thus, an optimal flow is a greatest matching. The creation of the new graph is O(m+n), and the capacity out of the source is O(n). Thus, it takes O(mn) (referring back to the FFA running time).

No questions.

No insights.

No complaints.

The algorithm can also handle distributed sources and sinks (each node has a supply or demand associated with it). Add a source with edges to each supply node with capacity equal to the supply of the incident node, and likewise add a sink connected to demand nodes. A circulation exists iff the maximum flow through this graph equals the sum of supplies and the sum of demands. One can further generalize to have lower bounds for nodes; before modeling the supply and demand, increase the demand of origin nodes of edges with lower bounds by that bound, and likewise decrease the demand of the destination nodes, and then solve as above for a maximum flow.

No questions.

No insights.

No complaints.