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.
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 .
- 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 .
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 .