Questions: Maximum Flow: Network Flow Problems and Algorithms

Question 1

In the Ford-Fulkerson method, why is the residual graph's reverse edge essential?

• A. It prevents the algorithm from visiting the same node twice
• B. It allows the algorithm to undo a previous flow decision and reroute flow more efficiently
• C. It records edges that have been fully saturated so they are skipped
• D. It doubles the capacity of each edge to handle bidirectional traffic

Answer: (B)

The residual graph's reverse edge is the key mechanism that makes Ford-Fulkerson correct. A greedy augmenting path choice might push flow along a suboptimal route. The reverse edge — with capacity equal to the current flow on that edge — lets a later augmenting path effectively 'cancel' earlier flow by routing through the reverse edge, redirecting that flow elsewhere. Without reverse edges, the algorithm could get permanently stuck at a suboptimal solution.

Question 2

After running Ford-Fulkerson to completion, which of the following is guaranteed to be true?

• A. The maximum flow equals the total capacity of all edges leaving the source
• B. The maximum flow equals the minimum capacity cut separating source from sink
• C. Every edge in the network carries flow equal to its capacity
• D. The number of augmenting paths found equals the maximum flow value

Answer: (B)

The max-flow min-cut theorem states that the maximum flow from source to sink equals the minimum capacity of any cut that separates source from sink. This is not just a convenient fact — it means solving max-flow simultaneously solves min-cut. Option A is wrong because not all source edges need to be fully used; option C is wrong because many edges may carry less than capacity; option D conflates the count of paths with the flow value.

Question 3

Edmonds-Karp guarantees polynomial time termination even when Ford-Fulkerson with DFS might not terminate.

• T. True
• F. False

Answer: True

Edmonds-Karp uses BFS to always choose the shortest augmenting path (fewest edges), which guarantees at most O(VE) augmentations and O(VE²) total time — regardless of capacity values. Basic Ford-Fulkerson with DFS can fail to terminate when edge capacities are irrational numbers, because augmenting paths can approach the maximum flow asymptotically without ever reaching it.

Question 4

Many combinatorial problems like bipartite matching require their own specialized algorithms and can seldom be reduced to max-flow.

• T. True
• F. False

Answer: False

This is a common misconception. Bipartite matching, edge-disjoint paths, circulation with lower bounds, and many scheduling problems all reduce to max-flow. For bipartite matching, you add a super-source connected to one partition and a super-sink connected to the other, set all capacities to 1, and run max-flow. The maximum flow value gives the maximum matching size. Recognizing problems as disguised max-flow instances is one of the most valuable skills in algorithm design.

Question 5

Why is the residual graph the central data structure in maximum flow algorithms, and what role do its reverse edges play?

Model answer: The residual graph tracks how much additional flow can be pushed along each edge. For a forward edge with capacity c carrying flow f, the residual capacity is c−f (remaining room). The reverse edge carries capacity f, representing the ability to 'undo' up to f units of flow. This is essential because greedy path choices may be locally good but globally suboptimal. By routing flow through a reverse edge, a later augmenting path effectively cancels and reroutes earlier flow, correcting those mistakes without explicit backtracking.

Without the residual graph and its reverse edges, the algorithm would be a simple greedy path-packer with no correction mechanism. The reverse edge is what transforms Ford-Fulkerson from a heuristic into an exact algorithm. Every correct max-flow algorithm implicitly or explicitly maintains this structure.