Questions: Advanced Network Flow Algorithms

Question 1

The push-relabel algorithm maintains a 'preflow' where flow into a vertex can exceed flow out (creating excess). Why is this approach faster than augmenting-path methods like Edmonds-Karp?

• A. Preflows require fewer total operations than augmenting paths
• B. Push-relabel operates locally — each push or relabel operation modifies a single vertex's excess or label in O(1) time, avoiding the global BFS that augmenting-path methods require for each augmentation. The total work across all operations is bounded by O(V^2 * E) through amortized analysis of relabel operations
• C. Push-relabel uses less memory than augmenting-path methods
• D. Preflows are always closer to the maximum flow than partial flows

Answer: (B)

Augmenting-path methods like Edmonds-Karp perform O(VE) augmentations, each requiring a BFS costing O(E), for O(VE^2) total. Push-relabel avoids global BFS entirely: it processes vertices with excess flow locally, pushing flow along edges to neighbors or relabeling (raising height) when no downhill push is possible. The height labels (a potential function) ensure progress: the total number of relabels is O(V^2), each non-saturating push decreases the total potential, and saturating pushes are bounded by O(VE). The resulting O(V^2 E) bound improves on Edmonds-Karp's O(VE^2) for dense graphs.

Question 2

Dinic's algorithm on unit-capacity networks runs in O(E * sqrt(V)) time, which is optimal for maximum bipartite matching. Why does unit capacity improve the runtime from O(V^2 E)?

Model answer: In unit-capacity networks, each augmenting path carries exactly 1 unit of flow and saturates at least one edge. After sqrt(V) phases of blocking flow (each computed in O(E) time on the layered graph), the maximum flow value increases by at most sqrt(V) more units — because the remaining augmenting paths have length > sqrt(V) and are therefore few in number (at most sqrt(V), since the paths are edge-disjoint in a unit graph). So the total number of phases is O(sqrt(V)), each costing O(E), giving O(E * sqrt(V)) total. For bipartite matching (a unit-capacity flow problem), this gives the Hopcroft-Karp bound of O(E * sqrt(V)).

The argument is subtle: after sqrt(V) phases, remaining augmenting paths are long (> sqrt(V) edges), and in a unit-capacity network, long edge-disjoint paths are scarce. This structural argument about path lengths is what gives the sqrt(V) bound on the number of additional flow units needed.

Question 3

Every maximum flow problem can be formulated and solved as a linear program, but specialized flow algorithms are preferred because they exploit network structure for faster running times.

• T. True
• F. False

Answer: True

The max-flow LP has variables for flow on each edge, constraints for capacity and conservation, and maximizes total flow out of the source. A general LP solver runs in O(n^3.5 L) time (interior point) where n includes all edges and vertices. But flow algorithms exploit the total unimodularity of the constraint matrix (guaranteeing integer optimal solutions) and the network structure (BFS, layered graphs, height functions) to achieve O(V^2 E) or better. For a graph with millions of edges, the specialized algorithms are orders of magnitude faster. However, the LP formulation is valuable for theoretical analysis — LP duality directly yields the max-flow min-cut theorem.

Question 4

The max-flow min-cut theorem states that the maximum flow value equals the minimum cut capacity. This is a consequence of LP strong duality applied to the flow LP.

• T. True
• F. False

Answer: True

The max-flow LP has a dual that is exactly the min-cut LP (with variables on edges indicating whether they cross the cut, and constraints ensuring a valid s-t cut). LP strong duality guarantees that the optimal primal (max-flow) and dual (min-cut) values are equal. This gives a clean proof of the max-flow min-cut theorem and illustrates how LP duality produces combinatorial results. The total unimodularity of the flow constraint matrix further guarantees that the LP has an integer optimal solution, meaning the continuous LP directly yields the combinatorial max-flow.