1

Application of Max-flow min-cut theorem for
Computer Vision
Hariprasad.P.S (EE11B064), S.R.Manikandasriram (EE11B127)

Abstract—This paper reviews the Max-flow min-cut theorem
based graph cut algorithms particularly the Ford-Fulkerson
algorithm and its applications in Computer Vision and otherfields.

I.

I NTRODUCTION

Graph cut is a well studied concept in Graph Theory. Oneof the major applications of Graph cuts is in the field of
Computer Vision. Many fundamental problems in Computer
Vision can be reformulated as a Graph Cut problem and inparticular, a Max-flow min-cut problem. In this paper, wewill study the Ford-Fulkerson algorithm which is based on
Max-flow min-cut theorem. A mathematical formulation of
the Max-flow min-cut problem as a general graph cut problem
will be presented. The implementation of the Ford-Fulkerson
algorithm will be explained in detail and supported by pseudocode. We will take a brief overview of the various applicationsof this problem in the field of Computer Vision which will
justify the importance of Ford-Fulkerson Algorithm. Finally,a brief analysis of the time complexity of the algorithm willbe presented.
According to graph theory, a graph cut is the grouping ofnodes in a connected component into two disjoint subsets andthe weight of the cut is defined to be equal to the sum of theweights of edges that are present between the disjoint subsets.
If we consider the graph as a flow network, then an s − t
cut is defined as a graph cut which requires the source andsink nodes to be in different subsets. The weight of an s − t
cut is called as the capacity of the cut. For a given graphcontaining a source and a sink node, there are many possibles − t cuts. Thus a minimum cut is defined as that s − t cut
whose capacity is less than or equal to every other s − t cut
for the given graph.
II.

M AX - FLOW MIN - CUT THEOREM

Given a flow network, the Max-flow min-cut theorem statesthat the maximum flow between the source and sink nodes
equals the minimum capacity over all s − t cuts. While there
can be many s − t cuts with the same capacity, consequently
there can be multiple ways to assign flows in the network whileachieving the same maximum flow.
Consider a network N = (V, E) with node s as source andnode t as sink. Let c(u, v) denote the real valued capacity ofthe edge (u, v) ∈ E and similarly, let f (u, v) denote the realvalued flow between the nodes u and v. The network N mustsatisfy the following:

Fig. 1. An example of a flow network showing a min s-t cut. source: Princeton
Lecture notes

f (u, v) ≤ c(u, v)∀u, v ∈ Vf (u, v) = −f (v, u)∀u, v ∈ VXf (u, v) = 0∀u ∈ V − {s, t}v∈VThe value of the flow through this network for a given s − t
cut is given by:
X
X|f | =f (s, v) =f (v, t)v∈Vv∈VIn order to find the maximal flow, we can apply the FordFulkerson algorithm to determine the minimum s−t cut which
produces that maximum flow.
III. F ORD -F ULKERSON A LGORITHM
Ford-Fulkerson algorithm can be briefly described as continuously sending flow along paths through the flow networkfrom source to sink until there exists no path which has alledges with non-zero capacity remaining.
The structure of the algorithm is as follows:• Find augmenting path P in the residual network Nf .
• Find bottleneck capacity of P .
• Augment flow through P .
• Repeat until no augmenting path exists.
Residual Graph
After one iteration of assigning flow to edges constituting a valid path P from s to t, the residual graph
Nf is formed by re-computing the edge weights
to denote the remaining capacities which must be
strictly greater than zero. All residual edges with2Fig. 2. A flow network implementing Flow Fulkerson algorithm to computethe min s-t cut

weight equal to zero are removed in the residualgraph.
Augmenting Path
Given a residual graph Nf , an augmenting path P
is a valid path from s to t which can contributetowards increasing the overall flow from s to t.

satellites, and microwave towers operated by a telephone company. Airline scheduling and Baseball elimination are otherexamples which use this algorithm.
The Ford-Fulkerson algorithm particularly has a lot ofapplications in Image Processing and Computer Vision. Someof them are image segmentation, optical flow estimation, stereocorrespondence, etc. where the given problem is transformed
into a maximum flow minimum cut problem and then solved
using the Ford-Fulkerson algorithm.
In the image segmentation problem, there are n pixels,
where each pixel i can be assigned a foreground value fi ora background value bi . There is a penalty of pij if pixels i, j
are adjacent and have different assignments. The problem is toassign pixels to background or foreground such that the sumof their values minus the penalties is maximum.
Let P be the set of pixels assigned to foreground and Q be
the set of points assigned to background, then the problem canbe formulated as,max(g) =Xfi +i∈PPseudo CodeInputs: Given a Network G = (V, E) with flow capacity c, asource node s, and a sink node t
Output: Compute a flow f from s to t of maximum value
We define the residual network Gf (V, Ef ) to be thenetwork with capacity cf (u, v) = c(u, v) − f (u, v) and noflow
1. f (u, v) ← 0 for all edges (u, v)
2. While there is a path p from s to t in Gf , such thatcf (u, v) > 0 for all edges (u, v) ∈ p:
1. Find cf (p) = min{cf (u, v) : (u, v) ∈ p}
2. For each edge (u, v) ∈ p
1. f (u, v) ← f (u, v) + cf (p)2. f (v, u) ← f (v, u) − cf (p)XX

bi −i∈Qpij(1)

i∈P,j∈Q∪j∈P,i∈Q

This maximization problem can be formulated as a minimization problem instead, that is,min(g 0 ) =Xi∈P

fi +Xi∈QX

bi +pij(2)

i∈P,j∈Q∪j∈P,i∈Q

The above equations can be formulated as a maximum flow
minimum cut problem by constructing a network where thesource is connected to all the pixels with capacity fi , andthe sink is connected by all the pixels with capacity bi . Twoedges (i, j) and (j, i) with pij capacity are added between
two adjacent pixels. The s − t cut-set then represents thepixels assigned to the foreground in P and pixels assigned
to background in Q.
R EFERENCES

Complexity Analysis
When the capacities are integers, the runtime of FordFulkerson is bounded by O(Ef ) , where E is the number ofedges in the graph and f is the maximum flow in the graph.
However if the graph has irrational values, the flow might notconverge towards the maximum value and the algorithm runs
foreverIV. R EAL W ORLD A PPLICATIONSThere are numerous real world applications of maximum
flow and minimum cut. A common question about any network
is ”what is the maximum flow rate between some node in that
network and any other node?”. For example, traffic engineers
may want to know the maximum flow rate of vehicles from thedowntown car park to the freeway because this will influence
their decisions on whether to widen the roadways. Anotherexample might be the maximum number of simultaneous
telephone calls between two cities via the various land-lines,[1]

Ford, L. R.; Fulkerson, D. R. (1956). ”Maximal flow through a network”.
Canadian Journal of Mathematics 8: 399–404, MR 0079251[2]

Gass, Saul I.; Assad, Arjang (2005), ”1954 Max-flow min-cut theorem”,
An annotated timeline of operations research: an informal history,
International series in operations research and management science 75,
Springer-Verlag, p. 96, ISBN 978-1-4020-8112-5[3]

George T. Heineman, Gary Pollice, and Stanley Selkow (2008). ”Chapter
8:Network Flow Algorithms”. Algorithms in a Nutshell. Oreilly Media.
pp. 226250. ISBN 978-0-596-51624-6[4]

http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf