Skip to content

Notations

Directed graph \(G=(V,E)\), source node \(s\), sink node \(t\).

Each edge \(e\) has its own capacity \(c(e)\).

\(s-t\) flow: For each \(e\in E\), \(0\leq f(e)\leq c(e)\).

Observation: For each \(v\in V-\{s,t\}\), the in-flow always equals to out-flow.

The value of flow \(f\) is \(val(f)=\) sum of out-flow from \(s\) = sum of in-flow to \(t\).

Max flow problem: Find the flow of graph \(G\) with maximum value.

Ford-Fulkerson Algorithm

The greedy algorithm doesn't work because when we fix the flow of a path, we can not withdraw some flow.

Residual Graph

Idea: When deciding to send the flow, we add a backward edge with same amount of flow, aka "undo" the flow sent: \(e^R\).

\(c_f(e)=\begin{cases}c(e)-f(e)\text{ for e}\\f(e)\text{ for }e^R\end{cases}\).

Augmenting path: a simple \(s-t\) path in residual graph.

Bottleneck capacity of an augmenting path \(p\) is the minimum residual capacity of any edges in \(p\).

Pseudocode

Initialization: \(f(e)=0\) for all edge \(e\in E\).

Repeat until no augment path on residual graph found:

  • Find augmenting path \(p\) in residual graph \(G\).
  • Augment the flow along path \(p\) on residual graph \(G\).

Running Time

Assume: capacity of an edge is integer and from \([0,C]\).

The algorithm terminates in at most \(n\cdot C\) iterations. There exists an BFS algorithm to find the augmenting path in \(O(m)\) time.

The overall running time is \(O(m\cdot n\cdot C)\). Which is not polynomial.

Choosing the Augmenting Path

How to choose augmenting path? Some choices lead to exponential time, some wise choices lead to polynomial time.

Capacity-scaling Algorithm

Find paths of high capacity first between \(s\) and \(t\).

Pseudocode

\(C_\max=\) max capacity edge. Start with \(D=C_\max\).

Start with zero flow

While \(D\geq 1\) repeat

  • \(G_f(D)=D\)-residual graph.
  • While there is a \(s-t\) path in \(G_f(D)\) where flow can be increase: increase flow along the path, update \(G_f(D)\).
  • \(D=D/2\)

\(D\)-residual graph is subgraph of residual graph with only edges with capacity \(\geq D\).

Running Time

To execute the algorithm, there are at most \(O(m\log C)\) iterations.

By using \(O(m)\) BFS to find the augmenting paths, it overall takes \(O(m^2\log C)\) time.

Edmonds Karp Algorithm

Find the shortest path along which flow can be increased.

Here shortest path is the shortest in terms of the number of edges.

Pseudocode

Start with zero flow.

Repeat

  • Find the shortest path from \(s\) to \(t\) along which flow can be increased.
  • Increase the flow along that path.

Running Time

Lemma 1: The length of the shortest path never decreases.

Lemma 2: After at most \(m\) augmentation of shortest path, the length of shortest augmenting path must increase.

It can be shown that this requires only \(O(mn)\) times, together with \(O(m)\) BFS, the overall running time is \(O(nm^2)\).

Unit-capacity Simple Network

Every edge has capacity of \(1\).

Every node has either \(1\) out-degree or \(1\) in-degree.

Ford-Fulkerson: \(O(mn)\)

Capacity scaling: \(O(m^2)\)

Shortest augmenting path: \(O(mn^2)\to O(m\sqrt n)\).

Bipartite Matching

A matching is a subset of edges \(M\subseteq E\), s.t., each node appears in at most one edge in \(M\).

Given a bipartite graph \(G\), find a max-cardinality matching.

Actually there is a equivalence between bipartite matching and max flow.

How to do:

  1. Make all edges directed from left hand side to right hand side.
  2. Add \(s\), and add \(n/2\) edges from \(s\) to all nodes on left hand side.
  3. Add \(t\), and add \(n/2\) edges from all nodes on right hand side to \(t\).
  4. Run max flow algorithm on the graph. The answer is equal to max-cardinality matching.

Perfect Matching

A matching that contains all the nodes from graph \(G\).

Observation: When does the perfect matching not exist?

If there exist a subset \(S\) of nodes on one side, that the number of neighbors of nodes in \(S\) on the right hand side is less than \(|S|\).