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.

Maximum Flow Algorithms

We understand now the optimality conditions for maximum flow well. But how about computing one? Observe: The Max-Flow Min-Cut theorem can be easily turned into an actual algorithm.

Computing Max Flow with Augmenting Paths

Natural algorithm: Repeatedly find augmenting paths in the residual graph.

• By Max-Flow Min-Cut theorem we know that either our flow is already optimal or there is an augmenting path to find.
• Each augmenting path computation can be easily done in $O(m)$ time.
• Key question: How many times we might need to find an augmenting path before we reach the max flow?
• Consider first the case of integer capacities. (This will be most often the case anyway.)
  • If capacities are integral then the bottleneck capacity of each augmenting path we find is integer and positive, so at least $1$.

    $\Rightarrow$ We have at most $|f|$ augmenting path computations, giving an $O(m|f|)$ overall bound.

  • Note that, by Max-Flow Min-Cut Theorem, \[ |f|=u(S^*)\leq u(\{s\})\leq nU, \] where $U:=\max_e u_e$ is the largest edge capacity.

    $\Rightarrow$ The overall running time is $O(mnU)$. Note: This running time is polynomial in the value of our input but not in the size of its binary representation. (Such algorithms are called pseudo-polynomial.) When $U=1$, this is polynomial time algorithm though.

  • Important corollary: If all capacities are integral then there exists an integral maximum flow too. (Although there could still exist maximum flows that are non-integral.)
• When capacities are rational, we can think of multiplying all capacities by the product of their denominators, and thus reduce to the integral capacity case.

  $\Rightarrow$ The running time is finite, but most likely not even pseudo-polynomial.

• When capacities are real numbers, we might not even have termination.

Sidenote: The above algorithm was simple to describe but its dynamics can be quite complex.

• Each augmentation constitutes a “greedy” improvement step, but these augmentations might undo/overwrite previous updates, adding flow to an edge and then removing it.
• Instructive example to look at: “diamond” graph with edges $(s, v)$, $(s,w)$, $(v,w)$, $(v,t)$, and $(w,t)$, and capacities being $1000$ on all the edges except $(v,w)$ which has a capacity of $1$. What will happen if we always choose an augmenting path going through the capacity $1$ edge? How does it compare to making a “smart” choice of the augmenting path?

Maximum Bottleneck Capacity Augmenting Paths

So far, we assumed that we just find an augmenting path. But maybe there is a “smart” way to choose one? Natural idea: Always choose an augmenting path $P$ that has maximum bottleneck capacity $u_f(P)$.

• How to find one? Actually, quite simple. Easy $O(m\log n)$-time algorithm: just do binary search over the capacity of “bottlenecking” edge and, for each guess $u$, check for $s$-$t$ path in $G_f$ after all the edges with capacity less than $u$ were removed. By being (much) more sophisticated, one can get $O(\min\{ m+n \log n, m \log^*n\})$ time.
• How much progress each such augmenting path guarantees to make?
• Recall: The flow decomposition bound tells us that any flow can be decomposed into at most $m$ flow paths.

  $\Rightarrow$ If we apply this observation to the maximum (remaining) flow, i.e., the maximum flow in the residual graph $G_f$ together with an averaging argument, we get that at least one of these paths carries at least $1/m$-fraction of the remaining value of the flow. (Note that all such paths have to be augmenting in $G_f$ by definition.)

  $\Rightarrow$ Each flow augmentation reduces the remaining value of the flow by a factor of $(1-1/m)$.

• After $m\ln |f| +1$ augmentations, the remaining flow would be less than $1$. So, if capacities are integral, the obtained solution has to be optimal. The overall running time is \[ O((m\log n)\cdot m \ln |f|)=O(m^2 \log n \log nU). \]
• Note: This is a “truly” polynomial running time, i.e., it is polynomial in the size of the representation of the input numbers. Still, sometimes one can ask for even more: running time that is independent of the input numbers, i.e., depends only on the size of the graph itself. This kind of algorithms are called strongly polynomial (and the ones that are only polynomial in the size of the numbers are called weakly polynomial).
• If capacities are rational, the above algorithm still has interesting properties. In particular, if $U$ will be now the largest denominator/enumerator in the capacities, then by multiplying all capacities by the product of all denominators and applying the algorithm above will give us a running time of \[ O((m\log n)\cdot m \ln |f|)=O(m^2 \log n \log nU^m)=O(m^3 \log n \log nU), \] which is still (weakly) polynomial. (Note: we do not actually need to explicitly multiply all capacities here.)

From now on: Unless stated otherwise, we assume that capacities are integral.