Mincut Problem

Given a edge-weighted (positive capacity) digraph, with a source vertex and a target vertex ,

Defs:

• An st-cut is a cut that partitions the vertices into one subset A containing and the other one B containing .
• A cut's capacity is the sum of the capacities of edges from A to B (don't count the edges from B to A).
• A minimum st-cut (mincut) problem is to find the cut with minimum capacity.

Maxflow Problem

Assume: no flow into and no flow out from

Defs:

• An st-flow (flow) is an assignment of flows to the edges s.t.
  • capacity constraint:
  • low equilibrium: for each vertex, flow in = flow out (except for and )
• the value of a flow is the sum of flows into
• maxflow problem is to find the flow with maximum value.

Maxflow-mincut Theorem

def: A net flow across a cut(A,B) is the sum of flows from A to B minus the sum of flows from B to A.

Flow-value Lemma: Let be any flow, and let (A,B) be any cut, then net flow across (A,B) = value of .
Pf:

• by induction, base case from B = {} when the net flow across (A,B) = inflows to = value of

• because of the local equilibrium, adding any other vertices into B won't change the net flow

  
  

Weak Duality: value of f cut capacity
Pf: value of f = (1) net flow across (A,B) (2) cut capacity:

• (1) because the flow-value lemma
• (2) note: given a cut(A, B), net flow is flow from A to B minus flow from B to A, but cut capacity only add up the capacities from A to B and never subtract anything.

Def: An augmenting path is an undirected path from to that no forward edge is full and no backward edge is empty.

Augmenting Path Theorem: A flow is the maxflow iff no augmenting paths.
Maxflow-mincut Theorem: Value of the maxflow = capacity of the Mincut.
Pf: Show the following three conditions are equivalent for any flow :

1. There's a cut whose capacity = the value of flow
2. is a maxflow
3. no augmenting paths w.r.t

value of cut capacity (weak duality), so the equality holds when is the maxflow.
if there's another augmenting path, there'll be another flow with a larger value, so is not a maxflow, so contradiction.

• no augmenting paths means is blocked from by some full forward edges and some empty backward edges
• so can find a cut (A,B) where the edges between A and B are all full/empty edges (if not, there can be an augmenting path through that non-full/non-empty edge, so contradiction)
• then, the capacity of that cut = sum of edge capacities from A to B = sum of edge flows from A to B (edges are full)
• the net flow across (A,B) = sum of edge flows from A to B - sum of edge flows from B to A ( which is 0 since backward edges are empty so the flows = 0)
• therefore, the capacity of (A,B) = the net flow across (A,B) = value of f
• and by weak duality (value of f cut capacity), the capacity is min. and the cut is the mincut.

Ford-Fulkerson algorithm

• Start from 0 flow
• While there's another augmenting path:
  • find an augmenting path
  • calculate the bottleneck capacity of that path
  • increase flow on that path by bottleneck capacity

Simplification: the edge capacities and flows are all integers, so that: Number of augmentations the value of the maxflow.

Potential Problem:

Using the augmenting paths through the capacity 1 edge will make the number of augmentations rather large

Solution: use shortest/fattest path

Implementation (shortest path version)

Flow Edge API

Use Residual capacity:

• forward:
• backward:
  i.e. convert edges from:
  
  to:

FlowEdge API

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

public void addResidualFlowTo(int v, double delta) {
    if (v == from()) { this.flow -= delta; }
    if (v == to()) { this.flow += delta; }
    throw new IllegalArgumentException();
}

Flow Network API

-- similar to the implementation of an undirected graph:

• adjacency-lists representation
• add edge to both and (even if has direction)

Find augmenting path:

shortest path version uses BFS

private boolean hasAugmentingPath(FlowNetwork G, int s, int t) {
    edgeTo = new FlowEdge[G.V()];
    marked = new boolean[G.V()];
    Queue<Integer> q = Queue<>(); // queue for BFS
    q.enqueue(s); // start from the source
    while (!q.isEmpty()) {
        int v = q.dequeue(); 
        for (FlowEdge e : G.adj(v)) {
            int w = e.other(v);
            // check is it full/empty or is it visited
            if (e.residualCapacityTo(w) > 0 && !marked[w]) {
                marked[w] = true;
                edgeTo[w] = e;
                q.enqueue(w);
            }
        }
    }
    return marked[t]; // whether target t can be reached
}

The Algorithm:

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()) {
            double bottle = INFINITY;
            // calculate the bottleneck capacity
            for (int v = t; v != s; v = edgeTo[v]) {
                bottle = Math.min(edgeTo[v].residualCapacityTo(v), bottle);
            }
            // augment flow
            for (int v = t; v != s; v = edgeTo[v]) {
                edgeTo[v].addResidualFlowTo(v, bottle);
            }
            value += bottle;
        }
    }
    
    private boolean hasAugmentingPath(FlowNetwork G, int s, int t) { 
        /* See method above. */ 
    }
}

Running time:

digraph with V vertices, E edges, and integer capacities between 1 and U

TO BE COMPLETED: two applications.