Network Flow

Idea: model a network as a graph where some material (water, data, etc) flows along edges, but each edge has a maximum capacity for flow.

_images/flow1.png

Like MST and shortest paths, many problems from many areas (e.g. transportation, communication, image processing) can be put in this form.

Flow Networks

A flow network is a directed graph \(G=(V,E)\) where each edge e has a nonnegative capacity \(c_e\) (for simplicity, assume capacities are integers).

There are also designated source and sink nodes \(s, t \in V\).

All other nodes are called internal nodes.

We assume every node has at least 1 edge connected to it (otherwise we remove it).

S-T Flow

An s-t flow (or simply “flow”) is a function \(f: E \to \mathbb{R}\) (where \(f(e)\) is the amount of flow along edge e) satisfying:

  1. For all \(e \in E, 0 \leq f(e) \leq c_e\) (flow does not exceed capacity

  2. For all internal nodes v, \(\sum_{(u, v)\in E} f(e)= \sum_{(v, u)\in E} f(e)\) (flow into v = flow out of v; conservation of mass)

_images/flow2.png

Flow into u: \(f(s, u) = 20\)

Flow out of u: \(f(u, v) + f(u, t) = 10 + 10 = 20\)

The value of a flow f is the total flow coming out of the source: \(v(f) = \sum_{(s, u) \in E} f(e)\).

In the example above, \(v(f) = f(s, u) + f(s, v) = 20 + 0 + 20\).

Maximum-Flow Problem

Given a flow network, find a flow with the largest possible value.

To solve this, there’s a natural greedy approach: given a flow, incrementally try to increase the flow along some path from s to t.

  1. Start with 0 flow at each edge: this is a valid flow.

  2. Given a path from s to t, look at the minimum capacity of edges along it: this is the bottleneck for adding flow along the path. Add this much flow along each edge.

Ex: Consider the path \((s, u, v, t)\). Minimum capacity is 20, so we could “push” 20 units of flow along the path to get a flow of higher value.

_images/flow3.png

We could then try to push more flow along a different path, etc. However, in this example, we get stuck! There are no more paths we can push flow on, but this flow is not optimal.

In order to get an optimal flow (of value 30 in this example), we would need to decrease the flow from u to v from 20 to only 10. To keep track of which edges can be increased or decreased, we use the residual graph.

The residual graph \(G_f\) of a flow f has the same vertices as G, and for every edge \(e = (u, v)\) of G:

  1. If \(f(e) < c_e\), there is \(c_e - f(e)\) residual capacity (unused capacity), so we add a forward edge \((u, v)\) to \(G_f\) with capacity \(c_e - f(e)\).

  2. If \(f(e) > 0\), we could decrease the flow by up to \(f(e)\), so we add a backward edge \((v, u)\) to \(G_f\) with capacity \(f(e)\).

Ex: In the flow above, \(G_f\) is:

_images/flow4.png

Note

For each edge of G, there can be 1 or 2 edges in \(G_f\).

We’ll call a path from s to t in \(G_f\) which doesn’t repeat vertices an augmenting path. Given such a path, we can augment the flow f as follows: if b is the weight of the least-weight edge along the path, then we consider each edge of the path in turn:

  • if it is a forward edge, increase the flow along it in G by b

  • if it is a backward edge, decrease the flow along the reverse edge in G by b.

_images/flow5.png

Lemma: The result of augmenting a flow along any augmenting path is a valid flow of higher value.

This then enables a greedy approach to max flow:

Ford-Fulkerson Method

  • start with the all-zero flow f

  • while there is a path from s to t in \(G_f\):
    • take any augmenting path p

    • augment f along p

  • return f

_images/flow6.png

Termination and Runtime

Invariant: Flow along each edge is an integer.

  • True initially, since we start with the all-zero flow

  • If true at one iteration, the residual capacities are all integers since the flows and capacities are integers. So the bottleneck b is an integer, and the new flow will all be integers.

So the value of the flow increases every iteration (see lemma) and is an integer, and since it can’t exceed \(\sum_{e=(s,v)\in E}c_e\), the value of the flow has to eventually stop growing so the loop must eventually terminate.

If the value of the maximum flow is F, there are in fact at most F iterations, since \(b \geq 1\). So if the network has n vertices and m edges, we can implement FF in \(O(mF)\) time:

  1. Building the residual graph takes \(O(n+m)\) time, which is \(O(m)\) since each vertex has at least one edge

  2. Finding an augmenting path with BFS/DFS takes \(O(m)\) time

  3. Augmenting the flow requires iterating over the path and takes \(O(m)\)

Optimality

Idea: Flow from s to t cannot exceed the total capacity of edges crossing a cut which separates s from t.

_images/flow7.png

A partition of V into two sets \((A, B)\) with \(s\in A, t\in B\) is an s-t cut.

The capacity of the cut is the total capacity of all edges from A to B:

\[\begin{split}c(A,B) & =\sum_{e=(u, v)\in E, u \in A, v \in B}c_e \\ & = \sum_{e \text{ out of } A}c_e\end{split}\]

Given a flow f, let \(f^{out}(A) = \sum_{e \text{ out of } A} f(e)\) and \(f^{in}(A) = \sum_{e \text{ into } A} f(e)\)

Lemma

\(v(f)=f^{out}(A)-f^{in}(A)\)

Proof: By definition, \(v(f)=f^{out}(s)\). Also \(f^{in}(s)=0\) since s has no incoming edges. So \(v(f)=f^{out}(s)-f^{in}(s)\). Also, by conservation of flow, for any \(v \in A\) besides s, \(f^{out}(v)=f^{in}(v)\). So \(v(f)=\sum_{v\in A}(f^{out}(v)-f^{in}(v))\). Now consider the contribution of every edge \(e=(u, v)\) to this sum:

  • If an edge from A to A, its flow \(f(e)\) appears as a positive term in \(f^{out}(u)\) and a negative term in \(f^{in}(v)\), which cancel out.

  • If an edge from A to B, it contributes \(f(e)\) to the sum

  • If an edge from B to A, it contributes \(-f(e)\)

  • If an edge from B to B, it contributes 0

So the sum is equivalent to

\[\begin{split}& \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ into } A} f(e) \\ & = f^{out}(A)-f^{in}(A).\end{split}\]

Corollary: For any flow f and s-t cut \((A, B), v(f)\leq c(A, B)\).

Theorem

When FF algorithm returns f, there is an s-t cut \((A, B)\) such that \(v(f)=c(A,B)\).

Proof: When FF terminates, there is no path from s to t in \(G_f\). So if A is all vertices reachable from s in \(G_f\), and B is all other vertices, \((A, B)\) is an s-t cut.

There are no edges from A to B in \(G_f\), since otherwise the destination in B would be reachable from s.

So for any edge e from A to B in the original graph G, we must have \(f(e)=c_e\), since otherwise there would be a forward edge from A to B in \(G_f\).

Likewise, for any edge e from B to A in G, we must have \(f(e)=0\), since otherwise there would be a backward edge from A to B in \(G_f\).

Now by earlier lemma:

\[\begin{split}v(f) & = f^{out}(A) - f^{in}(A) \\ & = \sum_{e \text{ out of } A} f(e) - \sum_{e \text{ into } A} f(e) \\ & = \sum_{e \text{ out of } A} c_e \\ & = c(A, B).\end{split}\]

Corollary: Since no flow has value greater than the capacity of a cut, the flow returned by FF is optimal.

Corollary: The cut \((A, B)\) from the theorem above is a minimum cut: its capacity is as small as possible. (If there were one with a smaller capacity, the flow would have to have a smaller value)

This means we can use FF to find a minimum s-t cut in a graph: run it to find the flow f, then build \((A, B)\) as in the theorem.

Theorem (Max-Flow Min-Cut): In any flow network, the maximum value of an s-t flow is the minimum value of an s-t cut.

Note

Since FF always finds a flow with integer flows on all edges, there is always a maximum flow of this form.

Runtime Revisited

Our runtime bound of \(O(mF)\) with F being the value of the max-flow isn’t good when the capacities in the network are large (F could be large). But it turns out that if you use BFS to find the shortest augmenting path, the algorithm takes at most \(O(nm^2)\) time.

This choice of path is called the Edmonds-Karp algorithm.

Applications

  • Routing problems (get data from point A to B, maximizing throughput)

  • Matching problems, e.g. bipartite matching

Bipartite Matching

Suppose we have n workers with different skills, and various jobs to do which some subsets of the workers are qualified to do. We want to assign workers to jobs so that as many jobs get done as possible, with no worker assigned multiple jobs and no job assigned multiple workers.

Model this problem using a bipartite graph: vertices for workers and jobs, with edges indicating who can do which jobs.

_images/flow8.png

Then we want to find a maximum matching: a set of edges M where no two edges share a vertex and is as large as possible.

_images/flow9.png

Idea: construct a network for instance such that the maximum flow is obtained by matching as many workers to jobs as possible.

Think of each worker as having 1 unit of work, which can be allocated to any of the jobs they can perform.

  • Add source node s and capacity 1 edges to each worker

  • Add capacity 1 edges from each worker to each possible job they can do

  • Add capacity 1 edges from each job to a sink node t

_images/flow10.png

To show this works, need to prove 2 directions:

  • If there is a matching with k edges, there is a flow of value k: flow 1 unit to each of the k workers assigned a job, then along the matched edges to their corresponding jobs, then to t.

  • Conversely, given a maximum flow with value k from FF, we can assume all flows on all edges are integers. Then there must be k jobs with 1 unit of flow coming out, and the rest have 0.

    • For those k jobs, they must have 1 unit of flow coming from a unique worker.

    • We can assign that worker to this job and get a valid assignment.

So every maximum matching corresponds to a maximum flow, and vice versa, and we can use FF to find such max a flow, and reconstruct the matching.

Since the maximum flow value is at most n (all workers assigned to jobs), the runtime of FF will be \(O(nm)\).

Image Segmentation

Suppose we want to identify which parts of an image are foreground/background, e.g. separating people from scenery.

_images/flow11.png

Two types of criteria for deciding if a pixel is a part of the foreground:

  1. A pixel may be more likely to be foreground due to color, position in image, etc. Say we have nonnegative likelihoods \(a_i\) and \(b_i\) for pixel i being foreground/background.

  2. A pixel which is adjacent to other foreground pixels is likely in the foreground. For each pair \((i, j)\) of adjacent pixels, say we have a penalty \(p_{ij} \geq 0\) for putting one in the foreground but not the other.

The best segmentation is then a partition of the pixels \((A, B)\) maximizing

\[\begin{split}q(A, B) = \sum_{i\in A} a_i + \sum_{j \in B} b_j - \sum_{(i, j) \text{ adjacent} \\ \text{1 in A}} p_{ij}\end{split}\]

Solving

To find the best partition, we observe that segmentations look like cuts in a graph, since they both partition pixels/vertices into 2 disjoint groups.

Can we set up a flow network s.t. the best segmentation corresponds to a minimum cut?

Issue: need to maximize \(q\), not minimize. But notice that \(q(A, B)\) is at most \(Q=\sum_i (a_i+b_i)\). So let’s minimize:

\[\begin{split}q'(A, B) = Q-q(A,B) = \sum_{i\in A} b_i + \sum_{j \in B} a_j + \sum_{(i, j) \text{ adjacent} \\ \text{1 in A}} p_{ij}\end{split}\]

Now we need to encode \(q'(A,B)\) as the capacity of a cut in some network.

We’ll add source and sink vertices s and t, and think of an s-t cut \((A, B)\) as representing a segmentation where all pixels in A are in the foreground, and the rest are in the background. We’ll encode each item above as the capacity of an edge crossing the cut.

  • Add an edge from pixel i to the sink t with capacity \(b_i\): then if \(i \in A\), since \(t\in B\), we will get a contribution of \(b_i\) to the capacity of the cut.

  • Add an edge from s to j with capacity \(a_j\): then in \(j \in B\), since \(s\in A\), we will get a contribution of \(a_j\) to the capacity of the cut.

  • Add edges from pixel i to adjacent pixel j and vice versa with capacity \(p_{ij}\): then if \(i \in A\) but \(j \in B\) or vice versa, we get a contribution of \(p_{ij}\).

_images/flow12.png

Then the capacity of the cut \((A,B)\) equals \(q'(A,B)\), so the minimum cut in the flow network corresponds to the best segmentation. Therefore, to find \((A,B)\) we can run FF to find the maximum flow in the network and extract the corresponding minimum cut.