Lecture 4

Maximum Flow

Example 1: Ship cement from factory to building

Input $s$: source, $t$: destination

Graph with directed edges weights on each edge: capacity

Goal: Ship as much stuff as possible while obeying capacity constrains.

Graph: $(V,E)$ directed and weighted

• Unique source and sink nodes $\to s, t$
• Each edge has capacity $c(e)$ [Integer]

A valid flow assignment assigns an integer $f(e)$ to each edge s.t.

Capacity constraint: $0\leq f(e)\leq c(e)$

Flow conservation:

$E_{in}(v)$: set of incoming edges to $v$ $E_{out}(v)$: set of outgoing edges from $v$

Compute: Maximum Flow: Find a valid flow assignment to

Maximize $|F|=\sum_{e\in E_{in}(t)}f(e)=\sum_{e\in E_{out}(s)}f(e)$ (total units received by end and sent by source)

Additional assumptions

1. $s$ has no incoming edges, $t$ has no outgoing edges
2. You do not have a cycle of 2 nodes

A proposed algorithm:

1. Find a path from $s$ to $t$
2. Push as much flow along the path as possible
3. Adjust the capacities
4. Repeat until we cannot find a path

Residual Graph: If there is an edge $e=(u,v)$ in $G$, we will add a back edge $\bar{e}=(v,u)$. Capacity of $\bar{e}=$ flow on $e$. Call this graph $G_R$.

Algorithm:

• Find an "augmenting path" $P$.
  • $P$ can contain forward or backward edges!
• Say the smallest residual capacity along the path is $k$.
• Push $k$ flow on the path ($f(e) =f(e) + k$ for all edges on path $P$)
  • Reduce the capacity of all edges on the path $P$ by $k$
  • Increase the capacity of the corresponding mirror/back edges
• Repeat until there are no augmenting paths

Formalize: Ford-Fulkerson (FF) Algorithm

1. Initialize the residual graph $G_R=G$
2. Find an augmenting path $P$ with capacity $k$ (min capacity of any edge on $P$)
3. Fix up the residual capacities in $G_R$
   • $c(e)=c(e)-k,\forall e\in P$
   • $c(\bar{e})=c(\bar{e})+k,\forall \bar{e}\in P$
4. Repeat 2 and 3 until no augmenting path can be found in $G_R$.

def ford_fulkerson_algo(G,n,s,t):
    """
    Args:
        G: is the graph for max_flow
        n: is the number of vertex in the graph
        s: start vertex of flow
        t: end vertex of flow
    Returns:
        the max flow in graph from s to t
    """
    # Initialize the residual graph $G_R=G$
    GR=[defaultdict(int) for i in range(n)]
    for i in range(n):
        for v,_ in enumerate(G[i]):
            # weight w is unused
            GR[v][i]=0
    path=set()
    def augP(cur):
        # Find an augumentting path $P$ with capacity $k$ (min capacity of any edge on $P$)
        if cur==t: return True
        # true for edge in residual path, false for edge in graph
        for v,w in G[cur]:
            if w==0 or (cur,v,False) in path: continue
            path.add((cur,v,False))
            if augP(v): return True
            path.remove((cur,v,False))
        for v,w in GR[cur]:
            if w==0 or (cur,v,True) in path: continue
            path.add((cur,v,True))
            if augP(v): return True
            path.remove((cur,v,True))
        return False
    while augP(s):
        k=min([GR[a][b] if isR else G[a][b] for a,b,isR in path])
        # Fix up the residual capacities in $G_R$
        # - $c(e)=c(e)-k,\forall e\in P$
        # - $c(\bar{e})=c(\bar{e})+k,\forall \bar{e}\in P$
        for a,b,isR in path:
            if isR:
                GR[a][b]+=k
            else:
                G[a][b]-=k
    return sum(GR[s].values())

Proof of Correctness: Valid Flow

Lemma 1: FF finds a valid flow

• Capacity and conservation constrains are not violated
• Capacity constraint: $0\leq f(e)\leq c(e)$
• Flow conservation: $\sum_{e\in E_{in}(v)}f(e)=\sum_{e\in E_{out}(v)}f(e),\forall v\in V-\{s,t\}$

Proof: We proceed by induction on augmenting paths

Base Case

$f(e)=0$ on all edges

Inductive Case

By inductive hypothesis, we have a valid flow and the corresponding residual graph $G_R$.

Inductive Step:

Now we find an augmented path $P$ in $GR$, pushed $k$ (which is the smallest edge capacity on $P$). Argue that the constraints are not violated.

Capacity Constrains: Consider an edge $e$ in $P$.

• If $e$ is an forward edge (in the original graph)
  • by construction of $G_R$, it had left over capacities.
• If $e$ is an back edge with residual capacity $\geq k$
  • flow on real edge reduces, but the real capacity is still $\geq 0$, no capacity constrains violation.

Conservation Constrains: Consider a vertex $v$ on path $P$

1. Both forward edges
   • No violation, push $k$ flow into $v$ and out.
2. Both back edges
   • No violation, push $k$ less flow into $v$ and out.
3. Redirecting flow
   • No violation, change of $0$ by $k-k$ on $v$.

Proof of Correctness: Termination

Lemma 2: FF terminate

Proof:

Every time it finds an augmenting path that increases the total flow.

Must terminate either when it finds a max flow or before.

Each iteration we use $\Theta(m+n)$ to find a valid path.

The number of iteration $\leq |F|$, the total is $\Theta(|F|(m+n))$ (not polynomial time)

Proof of Correctness: Optimality

From Lemma 1 and 2, we know that FF returns a feasible solution, but does it return the maximum flow?

Max-flow Min-cut Theorem

Given a graph $G(V,E)$, a graph cut is a partition of vertices into 2 subsets.

• $S$: $s$ + maybe some other vertices
• $V-S$: $t$ + maybe some other vertices

Define capacity of the cut be the sum of capacity of edges that go from a vertex in $S$ to a vertex in $T$.

Lemma 3: For all valid flows $f$, $|f|\leq C(S)$ for all cut $S$ (Max-flow $\leq$ Min-cut)

Proof: all flow must go through one of the cut edges.

Min-cut: cut of smallest capacity, $S^*$. $|f|\leq C(S^*)$

Lemma 4: FF produces a flow $=C(S^*)$

Proof: Let $\hat{f}$ be the flow found by FF. Mo augmenting paths in $G_R$.

Let $\hat{S}$ be all vertices that can be reached from $s$ using edges with capacities $>0$.

and all the forward edges going out of the cut are saturated. Since back edges have capacity 0, no flow is going into the cut $S$.

If some flow was coming from $V-\hat{S}$, then there must be some edges with capacity $>0$. So, $|f|\leq C(S^*)$

Example 2: Bipartite Matching

input: Given $n$ classes and $n$ rooms; we want to match classes to rooms.

Bipartite graph $G=(V,E)$ (unweighted and undirected)

• Vertices are either in set $L$ or $R$
• Edges only go between vertices of different sets

Matching: A subset of edges $M\subseteq E$ s.t.

• Each vertex has at most one edge from $M$ incident on it.

Maximum Matching: matching of the largest size.

We will reduce the problem to the problem of finding the maximum flow

Reduction

Given a bipartite graph $G=(V,E)$, construct a graph $G'=(V',E')$ such that

Let $s$ connects to all vertices in $L$ and all vertex in $R$ connects to $t$.

$G'=G+s+t+$added edges form $S$ to $T$ and added capacities.

Proof of correctness

Claim: $G'$ has a flow of $k$ iff $G$ has a matching of size $k$

Proof: Two directions:

1. Say $G$ has a matching of size $k$, we want to prove $G'$ has a flow of size $k$.
2. Say $G'$ has a flow of size $k$, we want to prove $G$ has a matching of size $k$.

Conclusion: Maximum Flow

Problem input and target

Ford-Fulkerson Algorithm

• Execution: residual graph
• Runtime

FF correctness proof

• Max-flow Min-cut Theorem
• Graph Cut definition
• Capacity of cut

Reduction to Bipartite Matching

Example 3: Image Segmentation: (reduction from min-cut)

Given:

• Image consisting of an object and a background.
• the object occupies some set of pixels $A$, while the background occupies the remaining pixels $B$.

Required:

• Separate $A$ from $B$ but if doesn't know which pixels are each.
• For each pixel $i,p_i$ is the probability that $i\in A$
• For each pair of adjacent pixels $i,j,c_{ij}$ is the cost of placing the object boundary between them. i.e. putting $i$ in $A$ and $j$ in $B$.
• A segmentation of the image is an assignment of each pixel to $A$ or $B$.
• The goal is to find a segmentation that maximizes

Solution:

• Let's turn our maximization into a minimization
• If the image has $N$ pixels, then we can rewrite the objective as

because $N=\sum_{i\in A}p_i+\sum_{i\in A}(1-p_i)+\sum_{i\in B}p_i+\sum_{i\in B}(1-p_i)$ boundary

New maximization problem:

Now, this is equivalent ot minimizing

Second steps

• Form a graph with $n$ vertices, $v_i$ on for each pixel
• Add vertices $s$ and $t$
• For each $v_i$, add edges $S-T$ cut of $G$ assigned each $v_i$ to either $S$ side or $T$ side.
• The $S$ side of an $S-T$ is the $A$ side, while the $T$ side of the cur is the $B$ side.
• Observer that if $v_i$ goes on the $S$ side, it becomes part of $A$, so the cut increases by $1-p$. Otherwise, it become part of $B$, so the cut increases by $p_i$ instead.
• Now add edges $v_i\to v_j$ with capacity $c_{ij}$ for all adjacent pixels pairs $i,j$
• If $v_i$ and $v_j$ end up on opposite sides of the cut (boundary), then the cut increases by $c_{ij}$.
• Conclude that any $S-T$ cut that assigns $S\subseteq V$ to the $A$ side and $V\backslash S$ to the $B$ side pays a total of
  1. $1-p_i$ for each $v_i$ on the $A$ side
  2. $p_i$ for each $v_i$ on the $B$ side
  3. $c_{ij}$ for each adjacent pair $i,j$ that is at the boundary. i.e. $i\in S\ and\ j\in V\backslash S$
• Conclude that a cut with a capacity $c$ implies a segmentation with objective value $cs$.
• The converse can (and should) be also checked: a segmentation with subjective value $c$ implies a $S-T$ cut with capacity $c$.

Algorithm

• Given an image with $N$ pixels, build the graph $G$ as desired.
• Use the FF algorithm to find a minimum $S-T$ cut of $G$
• Use this cut to assign each pixel to $A$ or $B$ as described, i.e pixels that correspond to vertices on the $S$ side are assigned to $A$ and those corresponding to vertices on the $T$ side to $B$.
• Minimizing the cut capacity minimizes our transformed minimization objective function.

Running time

The graph $G$ contains $\Theta(N)$ edges, because each pixel is adjacent to a maximum of of 4 neighbors and $S$ and $T$.

FF algorithm has running time $O((m+n)|F|)$, where $|F|\leq |n|$ is the size of set of min-cut. The edge count is $m=6n$.

So the total running time is $O(n^2)$