Combinatorial Optimization: Finding Optimum Solution
- Breakdown approach
- Solution: Understand feasibility
- Optimum: Verifying that a solution is optimum
- And understanding how to improve one that is not optimum
- Finding: actually producing the optimum comes last.
Maximum Flow
Definitions
Tarjan: Data Structures and Network Algorithms
Ford and Fulkerson, Flows in Networks, 1962 (paper 1956)
Ahuja, Magnanti, Orlin Network Flows. Problem: do min-cost.
Problem: in a graph, find a flow that is feasible and has maximum value.
Directed graph, edge capacities $u(e)$ or $u(v,w)$. Why not $c$? reserved for costs, later. source $s$, sink $t$
Goal: assign a flow value to each edge:
- conservation: for every vertex $v$, $\sum_w g(v,w)-g(w,v)=0$, unless $v=s,t$
- capacity: $0 \le g(e) \le u(e)$ (flow is feasible/legal) (sometimes lower bound $l(e)$)
- Flow value $|f| = \sum_w g(s,w)-g(w,s)$ (in gross model).
Alternative: (net flow form)
- skew symmetry: $f(v,w) = -f(w,v)$
- conservation: for every vertex $v$, $\sum_w f(v,w)=0$, unless $v=s,t$
- capacity: $f(e) \le u(e)$ (flow is feasible/legal) (sometimes lower bound $l(e)$)
- Flow value $|f| = \sum_w f(s,w)$
Net flow cleaner for math but involves negative flows and makes lower-bound flows messy. Raw flow may fit intuition/reality better.
Water hose intuition. Also routing commodities, messages under bandwidth constraints, etc. Often “per unit time” flows/capacities.
Maximum flow problem: find flow of maximum value.
Path decomposition (another perspective):
- claim: any $s$-$t$ flow can be decomposed into paths/cycles with quantities
- proof: induction on number of edges with nonzero flow
- if $s$ has out flow, traverse flow outward from $s$
- till find an $s$-$t$ path or cycle (why can we? conservation) and kill
- if $t$ has in-flow (won't any more, but no need to prove) work backwards to $s$ or cycle and kill
- if some other vertex has outflow, find a cycle and kill
- corollary: flow into $t$ equals flow out of $s$ (global conservation)
- Note: every path is a flow (balanced).
- Note: decomposition of positive value
- i.e. never have paths traveling opposite each other
- Note: at most $m$ paths/cycles (zero out one edge's flow each time)
Decision question: is there nonzero feasible flow
- Suppose yes. consider one.
- decompose into paths
- proves there is a flow path
- Suppose no
- then no flow path
- consider vertices reachable from $s$
- they form a cut $(s\in S, t \in T={\overline S})$
- no edge crossing cut
What about max-flow?
- Need some upper bound to decide if we are maximal
- Consider any flow, and cut $(S,T)$
- decompose into paths
- every path leaves the cut (at least) once
- So, outgoing cut capacity must exceed flow value
- min cut is upper bound for max flow
Suppose have some flow. How can we send more?
- Might be no path in original graph
/|\ / | \ / | \ s / | \ \ | / t \ | / \ | / \|/
- Instead need residual graph:
- Suppose flow $f(v,w)$
- set $u_f(v,w) = u(v,w)-f(v,w)$ (decrease in available capacity)
- which means set $u_f(w,v) = u(w,v)+f(v,w)$ (increase in capacity indicates can remove $(v,w)$ flow
- If augmenting path in residual graph, can increase flow
- What if no augmenting path?
- Implies zero cut $(S,T)$ in residual graph
- Implies every $S$-$T$ edge is saturated
- i.e. cut is saturated
- consider path decomposition
- each path crosses the cut exactly once (cannot cross back because decomposition paths don't oppose each other)
- so flow crossing cut equals value of flow
- i.e. value of cut equals value of flow
- but (again by path decomposition) value of flow cannot exceed value of cut (because all paths cross cut)
- so flow is maximum
We have proven Max-flow Min-cut duality:
- Equivalent statements:
- $f$ is max-flow
- no augmenting path in $G_f$
- $|f| = u(S)$ for some $S$
Proof:
- if augmenting path, can increase $f$
- let $S$ be vertices reachable from $s$ in $G_f$. All outgoing edges have $f(e) = u(e)$ and incoming have $f(e)=0$
- since $|f| \le u(S)$ always, equality implies maximum
Another cute corollary:
- Net flow across any cut (in minus out) equals flow value
- True for a path as it must go out once more than in
- So true for a sum of paths
Note that max-flow and min-cut are witnesses to each others' optimality.