Network Flow Algorithms & Applications
Network Flow Algorithms & Applications
Network flow algorithms solve optimization problems on directed graphs with capacities. Beyond the basic max-flow, powerful generalizations include min-cost flow, multi-commodity flow, and b-flow. Polynomial algorithms — Edmonds-Karp $O(VE^2)$, push-relabel $O(V^2\sqrt{E}}$, scaling algorithms — solve practical problems in logistics, scheduling, and bipartite matching.
Flow Algorithms & Complexity
Ford-Fulkerson: augments along any $s$-$t$ path in residual graph; may not terminate for irrational capacities. Edmonds-Karp (BFS augmenting paths): $O(VE^2)$ — each BFS augmentation increases the shortest augmenting path length; at most $O(VE)$ augmentations each taking $O(E)$. Push-relabel: maintains a preflow (local excess); relabels to create augmenting opportunities; $O(V^2\sqrt{E})$.
Min-Cost Flow
Min-cost flow: find maximum flow with minimum total cost $\sum w(e)f(e)$. Equivalent to: cycle canceling (Bellman-Ford), successive shortest paths (Dijkstra with potentials), or network simplex (pivot algorithm). Applications: transportation problem (minimize shipping cost), assignment problem (minimize cost of matching), job scheduling (minimize completion time).
Example 1
Formulate the bipartite matching problem as a max-flow problem and solve it for $K_{3,3}$.
Solution: Add source $s$ connected to all left vertices with capacity 1; add sink $t$ connected to all right vertices with capacity 1; all bipartite edges have capacity 1. Max-flow = maximum matching size. For $K_{3,3}$ (complete bipartite): max-flow = 3 (perfect matching exists). Ford-Fulkerson finds 3 augmenting paths, one for each perfect matching edge.
Example 2
Describe the assignment problem and give the Hungarian algorithm.
Solution: $n$ workers, $n$ jobs, cost matrix $C_{ij}$. Minimize $\sum C_{\sigma(i),i}$ over permutations $\sigma$. Hungarian algorithm: subtract row/column minima; find maximum matching in zero-cost entries; if perfect matching, done; otherwise augment with minimum uncovered element. $O(n^3)$. This is min-cost bipartite matching, equivalent to min-cost flow.
Practice
- Prove that every integer-capacity network has an integer-valued max-flow (integrality theorem).
- Describe the multi-commodity flow problem and explain why it may not have an integer solution.
- Apply network flow to solve a scheduling problem: 5 jobs, 3 machines, processing time constraints.
- Show that the circulation problem (b-flow) can be reduced to standard max-flow.
Show Answer Key
1. Max-flow min-cut theorem (Ford-Fulkerson): augmenting paths increase flow by integer amounts (when capacities are integers). The algorithm terminates (max-flow is finite) with an integer-valued flow. More formally: LP relaxation of integer flow has an integer optimal because the constraint matrix is totally unimodular (incidence matrix of a directed graph). ✓
2. Multi-commodity flow: $k$ source-sink pairs share the same network. LP relaxation is solvable in polynomial time, but the integer version is NP-hard (even for $k=2$ on directed graphs). The integrality gap can be $\Omega(\sqrt{\log k})$. Example: two commodities on a triangle graph — fractional optimum exceeds integer optimum.
3. Model as bipartite graph: jobs on one side, machines on the other. Edge $(j,m)$ exists if machine $m$ can process job $j$ within time constraints. Add source $s \to$ each job (capacity 1), each machine $\to$ sink $t$ (capacity = max jobs per machine). Max-flow gives maximum assignment. For 5 jobs, 3 machines with specific constraints: solve the resulting network to find an assignment completing the most jobs.
4. Circulation with demands $b(v)$: add a super-source $S$ and super-sink $T$. For each node $v$ with $b(v)>0$ (supply), add edge $(S,v)$ with capacity $b(v)$. For $b(v)<0$ (demand), add edge $(v,T)$ with capacity $|b(v)|$. A feasible circulation exists iff max-flow from $S$ to $T$ saturates all edges from $S$ (and to $T$). Reduces to standard max-flow on the augmented network.