Maximum Flow

1.  Definitions:  

    --  Input : An edge-weighted digraph (edge capacity) , source vertex s, and target vertex t.

    --  st-cut : A partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.

    --  capacity of the cut (A, B) : The sum of the capacities of the edges from A to B. 

    --  Minimum st-cut (mincut) problem: Find a cut of minimum capacity.

 

2.  Maxflow problem ：

    --  Input: An edge-weighted (capacity) digraph , source vertex s, and target vertex t.

    --  An st-flow (flow) is an assignment of values to the edges such that:

        -  Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity.

        -  Local equilibrium: inflow = outflow at every vertex (except s and t).

    --  The value of a flow is the inflow at t.( we assume no edge points to s or from t. )

    --  Maximum st-flow (maxflow) problem: Find a flow of maximum value.

 

3.  Remarkable fact: Mincut problem and Maxflow problem are dual!

 

4.  Ford-Fulkerson algorithm

    --  Initialization: Start with 0 flow.

    --  Find an augmenting path : undirected path from s to t such that:

        --  Can increase flow on forward edges (not full).

        --  Can decrease flow on backward edge (not empty).

    --  Increase flow along augmenting paths

    --  Termination: No augmenting path : All paths from s to t are blocked by either a

        --  Full forward edge.

        --  Empty backward edge.

 

 

5.  Relationship between flows and cuts:

    --  The net flow across a cut (A, B) is the sum of the flows on its edges from A to B minus the sum of the flows on its edges from from B to A.

    --  Flow-value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.

        --  Pf. By induction on the size of B.

            -  Base case: B = { t }.

            -  Induction step: remains true by local equilibrium when moving any vertex from A to B.

    --  Weak duality: Let f be any flow and let (A, B) be any cut. Then, the value of the flow ≤ the capacity of the cut.

        --  Pf. Value of flow f = net flow across cut (A, B) ≤ capacity of cut (A, B).

 

6.  Maxflow-mincut theorem

    --  Augmenting path theorem: A flow f is a maxflow iff no augmenting paths.

    --  Maxflow-mincut theorem. Value of the maxflow = capacity of mincut.

    --  Pf. The following three conditions are equivalent for any flow f :

        i. There exists a cut whose capacity equals the value of the flow f.

        ii. f is a maxflow.

        iii. There is no augmenting path with respect to f.

        --  [ i ⇒ ii ]

            -  Suppose that (A, B) is a cut with capacity equal to the value of f.

            -  Then, the value of any flow f ' ≤ capacity of (A, B) = value of f.

            -  Thus, f is a maxflow.

        --  [ ii ⇒ iii ] We prove contrapositive: ~iii ⇒ ~ii.

            -  Suppose that there is an augmenting path with respect to f.

            -  Can improve flow f by sending flow along this path.

            -  Thus, f is not a maxflow.

        --  [ iii ⇒ i ]

            -  Suppose that there is no augmenting path with respect to f.

            -  Let (A, B) be a cut where A is the set of vertices connected to s by an undirected path with no full forward or empty backward edges.

            -  By definition, s is in A; since no augmenting path, t is in B.

            -  Capacity of cut = net flow across cut = value of flow f.

 

7.  Computing a mincut from a maxflow:

    --  By augmenting path theorem, no augmenting paths with respect to f.

    --  Compute A = set of vertices connected to s by an undirected path with no full forward or empty backward edges.

 

8.  Does FF always terminate?

    yes, provided edge capacities are integers (or augmenting paths are chosen carefully)

 

9.  Ford-Fulkerson algorithm with integer capacities :

    --  Important special case: Edge capacities are integers between 1 and U.

    --  Invariant: The flow is integer-valued throughout Ford-Fulkerson.

        -- Pf. [by induction]

            -  Bottleneck capacity is an integer.

            - Flow on an edge increases/decreases by bottleneck capacity.

    --  Proposition. Number of augmentations ≤ the value of the maxflow.

        --  Pf. Each augmentation increases the value by at least 1.

    --  Integrality theorem. There exists an integer-valued maxflow.

        --  Pf. Ford-Fulkerson terminates and maxflow that it finds is integer-valued.

    --  Bad news : Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow.

    --  Good news : This case is easily avoided. [use shortest/fattest path]

 

10.  FF performance depends on choice of augmenting paths :

 

11.  Implementation Considerations of FF:

    --  Flow edge data type: Associate flow fe and capacity ce with edge e = v→w.

    --  Flow network data type: Need to process edge e = v→w in either direction: Include e in both v and w's adjacency lists.

    --  Residual capacity:

        -  Forward edge: residual capacity = ce - fe.

        -  Backward edge: residual capacity = fe.

    --  Augment flow.

        -  Forward edge: add Δ.

        -  Backward edge: subtract Δ.

    --  Residual network : Augmenting path in original network is equivalent to directed path in residual network.

 

12.  Flow edge: Java implementation:

public class FlowEdge
{
    private final int v, w; // from v to w
    private final double capacity; // capacity
    private double flow; // flow

    public FlowEdge(int v, int w, double capacity)
    {
        this.v = v;
        this.w = w;
        this.capacity = capacity;
    }

    public int from() { return v; }
    public int to() { return w; }
    public double capacity() { return capacity; }
    public double flow() { return flow; }
    public int other(int vertex)
    {
        if (vertex == v) return w;
        else if (vertex == w) return v;
        else throw new RuntimeException("Illegal endpoint");
    }

    public double residualCapacityTo(int vertex)
    {
        if (vertex == v) return flow; // from w to v , backward edge
        else if (vertex == w) return capacity - flow; // from v to w, forward edge
        else throw new IllegalArgumentException();
    }

    public void addResidualFlowTo(int vertex, double delta)
    {
        if (vertex == v) flow -= delta; //backward edge
        else if (vertex == w) flow += delta; //forward edge
        else throw new IllegalArgumentException();
    }
}

 

13.  Flow network: Java implementation :

public class FlowNetwork
{
    private final int V;
    private Bag<FlowEdge>[] adj;
    public FlowNetwork(int V)
    {
        this.V = V;
        adj = (Bag<FlowEdge>[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag<FlowEdge>();
    }

    public void addEdge(FlowEdge e)
    {
        int v = e.from();
        int w = e.to();
        adj[v].add(e);
        adj[w].add(e);
    }

    public Iterable<FlowEdge> adj(int v)
    { return adj[v]; }
}

 

14.  Ford-Fulkerson: Java implementation :

public class FordFulkerson
{
    private boolean[] marked; // true if s->v path in residual network
    private FlowEdge[] edgeTo; // last edge on s->v path
    private double value; // value of flow
    
    public FordFulkerson(FlowNetwork G, int s, int t)
    {
        value = 0.0;
        while (hasAugmentingPath(G, s, t))
        {
            double bottle = Double.POSITIVE_INFINITY;
            for (int v = t; v != s; v = edgeTo[v].other(v))
                bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
            for (int v = t; v != s; v = edgeTo[v].other(v))
                edgeTo[v].addResidualFlowTo(v, bottle);
            value += bottle;
        }
    }

    public double value()
    { return value; }

    public boolean inCut(int v)
    { return marked[v]; }

    private boolean hasAugmentingPath(FlowNetwork G, int s, int t)
    {
        edgeTo = new FlowEdge[G.V()];
        marked = new boolean[G.V()];
        Queue<Integer> queue = new Queue<Integer>();
        queue.enqueue(s);
        marked[s] = true;
        while (!queue.isEmpty())
        {
            int v = queue.dequeue();
            for (FlowEdge e : G.adj(v))
            {
                int w = e.other(v);
                if (e.residualCapacityTo(w) > 0 && !marked[w])
                {
                    edgeTo[w] = e;
                    marked[w] = true;
                    queue.enqueue(w);
                }
            }
        }
        return marked[t];
    }
}

 

15.  Maxflow application on bipartite matching :

    --  Problem definition: (Given a bipartite graph, find a perfect matching.)

        -  N students apply for N jobs.

        -  Is there a way to match all students to jobs?

    --  Network flow formulation of bipartite matching :

        -  Create s, t, one vertex for each student, and one vertex for each job.

        -  Add edge from s to each student (capacity 1).

        -  Add edge from each job to t (capacity 1).

        -  Add edge from student to each job offered (infinite capacity).

 

    --  When no perfect matching, mincut explains why :

        Consider mincut (A, B).

        -  Let S = students on s side of cut.

        -  Let T = companies on s side of cut.

        -  Fact: | S | > | T |; students in S can be matched only to companies in T.

 

16.  Maxflow application on Baseball elimination problem :

    --  Problem definition: Which teams have a chance of finishing the season with the most wins?

 

    --  Observation. Answer depends not only on how many games already won and left to play, but on whom they're against.

    --  maxflow formulation : Remaining games flow from s to t.

 

    --   Team 4 not eliminated iff all edges pointing from s are full in maxflow.