22 Ford-Fulkerson with Integer Capacities, Applications of Max Flow (Max Bipartite Matching, Edge-Disjoint Paths, Image Segmentation)

Lecture from: 13.05.2025 | Video: Homelab

Wrapping Up Ford-Fulkerson

Before we begin new applications, let’s recap the key algorithmic results from last time.

Assumptions

• Let the network be $N=(V,A,c,s,t)$, a directed graph.
• $n=|V|$ and $m=|A|$.
• Capacities $c:A\to {\mathbb{N}}_0$ are non-negative integers.
• Let $U={\max }_{e\in A}c(e)$ be the largest capacity.

Observation: Upper Bound on Maximum Flow

From the definition of capacity and network structure, we know:

That is, the flow from the source can be bounded above by the total outgoing capacity, which in the worst case is $(n-1)$ edges with maximum capacity $U$.

Runtime Per Iteration

Each iteration of the Ford-Fulkerson algorithm:

• Searches for an $s$-$t$ path in the residual graph: $\mathcal{O}(m)$.
• Augments flow along the path: $\mathcal{O}(m)$.

Thus, each iteration takes $\mathcal{O}(m)$ time.

Integer Capacities ⇒ Guaranteed Progress

With integer capacities:

• Each augmentation increases flow by at least 1.
• So, total number of augmentations is $\le (n-1)U$.

Theorem (Ford-Fulkerson Termination)

If all capacities are integers, Ford-Fulkerson terminates in at most $(n-1)U$ iterations and returns an integer-valued maximum flow.

Total Time Complexity:

Why Integer Capacities Matter

If capacities are irrational (e.g., $\sqrt{2}$), augmenting paths might increase flow by arbitrarily small amounts. This could lead to infinite loops and non-termination. Integer capacities ensure each step contributes non-zero flow, making the algorithm finite.

Applications of Maximum Flows

Flows and cuts in graphs offer a powerful toolkit to solve a range of problems in discrete mathematics, computer science, and beyond. In this lecture, we explore three key applications:

1. Maximum Bipartite Matching
2. Edge-Disjoint Paths
3. Image Segmentation via Min-Cut

Each is reduced to a max-flow (or min-cut) instance, allowing us to apply efficient algorithms with guaranteed correctness.

1. Maximum Bipartite Matching

Problem Definition

Let $G=(U\cup W,E)$ be a bipartite graph, with disjoint vertex sets $U$ and $W$ and edge set $E\subseteq U\times W$.

A matching is a set of edges $M\subseteq E$ such that no two edges in $M$ share an endpoint.

The goal is to find a maximum matching - one of maximum cardinality.

Note: the first matching is a “maximal” matching, while the second is a “maximal and (cardinality) maximum. Similarly the third one is a maximum matching.

Flow Network Construction

We reduce the matching problem to a max-flow problem.

Let $n=|U|+|W|$. Construct a flow network $N=(V^{\prime },A,c,s,t)$ as follows:

• Let $V^{\prime }=U\cup W\cup s,t$.
• Add a directed edge $(s,u)$ with capacity $1$ for each $u\in U$.
• Add a directed edge $(u,w)$ with capacity $1$ for each $(u,w)\in E$.
• Add a directed edge $(w,t)$ with capacity $1$ for each $w\in W$.

All capacities are $1$, and the graph is directed.

Correctness of the Reduction

Let $f$ be a flow in $N$ of value $k$.

Claim:

The graph $G$ has a matching of size $k$ if and only if $N$ has a flow of value $k$.

Proof Sketch:

($\Rightarrow$) Given a matching $M$ of size $k$ in $G$, define a flow $f$:

• For each $(u,w)\in M$, set $f(s,u)=f(u,w)=f(w,t)=1$.
• All other flows are $0$.

This is a valid flow (capacities respected, flow conservation holds), and has total value $k$.

($\Leftarrow$) Given a flow $f$ of value $k$, we extract a matching:

• Because of unit capacities, all flows are $0$ or $1$.
• For each edge $(u,w)$ with $f(u,w)=1$, include $(u,w)$ in the matching.
• Since each vertex has in-degree and out-degree at most $1$, no two edges share an endpoint.

Hence, this defines a matching of size $k$.

Algorithm and Runtime

Apply Ford-Fulkerson (or a variant like Edmonds-Karp). Since all capacities are integers (in fact, 1), the integrality theorem guarantees an integer flow.

• Runtime: $\mathcal{O}(mn)$ for Ford-Fulkerson with unit capacities.
• Improved: Hopcroft-Karp algorithm solves it in $\mathcal{O}(\sqrt{n}m)$.

2. Edge-Disjoint Paths

Problem Definition

Let $G=(V,E)$ be a directed or undirected graph, and $u,v\in V$, $u\ne v$.

The task is to find the maximum number of edge-disjoint $u$-$v$ paths, i.e., simple paths from $u$ to $v$ that do not share any edge.

Reduction to Max-Flow

Construct a network $N=(V,A,c,u,v)$:

• Replace each undirected edge $x,y$ by directed edges $(x,y)$ and $(y,x)$.
• Set capacity $c(e)=1$ for all $e$.

Now compute a maximum flow from $u$ to $v$ in $N$.

Correctness

Let $f$ be a flow of value $k$.

We show that $G$ has $k$ edge-disjoint $u$-$v$ paths.

• Flow values are integral ($\in 0,1$).
• For any vertex $x\notin u,v$, the number of incoming edges with $f=1$ equals the number of outgoing edges with $f=1$ (flow conservation).
• Hence, paths can be extracted by tracing flow from $u$ to $v$.

Construction of Paths:

1. Start at $u$.
2. Follow outgoing edges with $f=1$.
3. Remove used edges from the flow.
4. Repeat until all flow is exhausted.

This results in $k$ edge-disjoint paths.

Theoretical Implication: Menger’s Theorem

This reduction gives an algorithmic proof of:

The maximum number of edge-disjoint $u$-$v$ paths equals the minimum number of edges whose removal separates $u$ and $v$.

This is a special case of the Max-Flow Min-Cut Theorem.

3. Image Segmentation via Min-Cut

Problem

We are given an image modeled as a graph $G=(P,E)$ where:

• $P$ = set of pixels
• $E$ = adjacency of neighboring pixels

Each pixel $p\in P$ has:

• ${\alpha }_p$: cost of assigning $p$ to the foreground
• ${\beta }_p$: cost of assigning $p$ to the background

Each edge $e=p,p^{\prime }\in E$ has:

• ${\gamma }_e$: cost of cutting this edge (i.e., separating $p$ and $p^{\prime }$)

Goal: Assign each pixel to foreground or background to minimize segmentation cost.

Objective Function

Let $(A,B)$ be a partition of $P$ into foreground and background.

We define the cost:

• First two terms: penalty for “wrong” label
• Last term: penalty for inconsistent adjacent labels

Flow Network Construction

Build a flow network $N=(V^{\prime },A,c,s,t)$:

• $V^{\prime }=P\cup s,t$
• For each pixel $p$:
  • Add edge $(s,p)$ with capacity ${\alpha }_p$
  • Add edge $(p,t)$ with capacity ${\beta }_p$
• For each edge $e=p,p^{\prime }$:
  • Add directed edges $(p,p^{\prime })$ and $(p^{\prime },p)$ with capacity ${\gamma }_e$

Solving the Segmentation

• Compute a minimum $s$-$t$ cut.
• Let $S$ be the set of vertices reachable from $s$ in the residual graph.
• Assign $A=S\setminus s$ to foreground, $B=P\setminus A$ to background.

Why Does This Work?

The capacity of the $s$-$t$ cut $(S,T)$ is exactly:

Hence, minimizing the cut minimizes the segmentation cost.

Summary

“Combinatorial problems often hide inside networks. Flows and cuts reveal their structure - and their solutions.”