• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Flow

    David Karger

    Combinatorial Optimization: Finding Optimum Solution

    Maximum Flow


    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:

    Alternative: (net flow form)

    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):

    Decision question: is there nonzero feasible flow

    What about max-flow?

    Suppose have some flow. How can we send more?

    What if no augmenting path?

    We have proven Max-flow Min-cut duality:

    Proof summary:

    Another cute corollary:

    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.

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

    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)\).

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