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.