PDF of Eric’s written notes are here.

In this lecture we’ll present the max-flow min-cut theorem and show an application of this theorem to the image segmentation problem.

**Flow network**

A flow network is defined by a directed graph with designated source and sink , along with a capacity for each .

is the flow along the edge . We want to maximize the flow from to .

Constraints:

- for all , (capability constraint)
- for all , flow-in = flow-out : (flow is conserved)

= total flow sent = flow-out = = flow-in = .

**Max-flow** problem: given a flow network, find a flow with . This is closely related to the following **min-cut** problem.

A *cut* is a partition of the vertices into two sets and such that and . This is an s-t cut if and . For an s-t cut, its capacity is defined as .

**Min st-cut problem**: given a flow network, find an s-t cut with minimum capacity.

**Max-flow min-cut theorem**:

size of max-flow = min capacity of an s-t cut.

We prove the theorem in two directions. The easy direction is that size of max-flow min capacity of an s-t cut. We’ll show that for any flow and any s-t cut , . Hence .

For an s-t cut , define , .

We show that

Therefore, for any flow and any s-t cut , , which proves .

Then we show that . Take the flow produced by the Ford-Fulkerson algorithm. has no augmenting path, which means that there is no s-t path in the residual network . We’ll construct an s-t cut where . Hence .

Proof of for flow , let be those vertices reachable from in . We know that since there is no s-t path in . Let and is a s-t cut.

Consider an edge from to : for where and , we must have , otherwise in and is reachable from , contradiction.

Consider an edge from to : for where and , we must have , otherwise and is reachable from , contradiction.

Thus, and . Therefore, , which proves .

We also know that any flow with no augmenting paths is a max-flow, since .

**Image segmentation**

Given an image, separate it into objects. A simpler problem: separate it into foreground and background. Image is on an undirected graph with and .

For , given likelihood that is in the foreground and that is in the background with . For , given separation penalty .

For a partition where (A = foreground, B = background), define its weight as .

**Goal**: find partition with maximum weight . We can reduce it to min s-t cut problem.

First, we convert it from a maximization to a minimization problem. Let (note that ). Thus, .

Let . that maximizes is the same as which minimizes .

To reduce to max-flow: for an edge : add edges with capacity and with capacity ; add source , for every add edges with capacity ; add sink , for every , add edge with capacity .

In this flow network, for an s-t cut , we ask what edges cross ? For , get an edge of capacity , for get an edge of capacity , for where , get an edge of capacity , and if , get an edge also of capacity .

Therefore, . So we run max-flow algorithm, the size of the max-flow =. Thus .