CSC373
Week 5: Network Flow (contd)
Nisarg Shah
373F20 – Nisarg Shah 1
Recap
• Some more DP
➢ Traveling salesman problem (TSP)
• Start of network flow ➢ Problem statement
➢ Ford-Fulkerson algorithm
➢ Running time
➢ Correctness using max-flow, min-cut
373F20 – Nisarg Shah 2
This Lecture
• Network flow in polynomial time
➢ Edmonds-Karp algorithm (shortest augmenting path)
• Applications of network flow
➢ Bipartite matching & Hall’s theorem
➢ Edge-disjoint paths & Menger’s theorem ➢ Multiple sources/sinks
➢ Circulation networks
➢ Lower bounds on flows
➢ Survey design
➢ Image segmentation
373F20 – Nisarg Shah 3
Ford-Fulkerson Recap
• Define the residual graph 𝐺 of flow 𝑓
➢ 𝐺 has the same vertices as 𝐺 𝑓
➢For each edge e = (𝑢,𝑣) in 𝐺, 𝐺 has at most two edges 𝑓
o Forward edge 𝑒 = (𝑢, 𝑣) with capacity 𝑐 𝑒 − 𝑓 𝑒 • We can send this much additional flow on 𝑒
o Reverse edge 𝑒𝑟𝑒𝑣 = (𝑣, 𝑢) with capacity 𝑓(𝑒)
• The maximum “reverse” flow we can send is the maximum
amount by which we can reduce flow on 𝑒, which is 𝑓(𝑒) o We only add each edge if its capacity > 0
𝑓
373F20 – Nisarg Shah 4
Ford-Fulkerson Recap
• Example!
Flow 𝑓 Residual graph 𝐺
uu
𝑓
20/20 0/10 𝟐𝟎 𝟏𝟎 s20/30t s𝟐𝟎𝟏𝟎t
0/10 20/20 𝟏𝟎 𝟐𝟎 vv
373F20 – Nisarg Shah 5
Ford-Fulkerson Recap
MaxFlow(𝐺):
// initialize:
Set𝑓𝑒 =0forall𝑒in𝐺
// while there is an 𝑠-𝑡 path in 𝐺 : 𝑓
While 𝑃 = FindPath(s, t,Residual(𝐺, 𝑓))!=None: 𝑓 = Augment(𝑓, 𝑃)
UpdateResidual(𝐺,𝑓)
EndWhile Return 𝑓
373F20 – Nisarg Shah 6
Ford-Fulkerson Recap
• Running time:
➢ #Augmentations:
o At every step, flow and capacities remain integers
oForpath𝑃in𝐺 ,bottleneck 𝑃,𝑓 >0impliesbottleneck 𝑃,𝑓 ≥1 𝑓
o Each augmentation increases flow by at least 1 o At most 𝐶 = σ𝑒 leaving 𝑠 𝑐(𝑒) augmentations
➢ Time for an augmentation:
o 𝐺 has 𝑛 vertices and at most 2𝑚 edges
o Finding an 𝑠-𝑡 path in 𝐺 takes 𝑂(𝑚 + 𝑛) time 𝑓
➢ Total time: 𝑂( 𝑚 + 𝑛 ⋅ 𝐶)
𝑓
373F20 – Nisarg Shah 7
Edmonds-Karp Algorithm
• At every step, find the shortest path from 𝑠 to 𝑡 in
𝐺 , and augment. 𝑓
MaxFlow(𝐺):
// initialize:
Set 𝑓 𝑒 = 0 for all 𝑒 in 𝐺
Minimum number of edges
// Find shortest 𝑠-𝑡 path in 𝐺 & augment: 𝑓
While𝑃= BFS(s,t,Residual(𝐺,𝑓))!=None: 𝑓 = Augment(𝑓, 𝑃)
UpdateResidual(𝐺,𝑓) EndWhile
Return 𝑓
373F20 – Nisarg Shah 8
Proof Overview
• Overview
➢ Lemma 1: The length of the shortest 𝑠 → 𝑡 path in 𝐺
never decreases. o (Proof ahead)
➢ Lemma 2: After at most 𝑚 augmentations, the length of the shortest 𝑠 → 𝑡 path in 𝐺 must strictly increase.
o (Proof ahead)
➢ Theorem: The algorithm takes 𝑂(𝑚2𝑛) time. o Proof:
• Lengthofshortest𝑠→𝑡pathin𝐺 cangofrom0to𝑛−1 𝑓
• Using Lemma 2, there can be at most 𝑚 ⋅ 𝑛 augmentations • Eachtakes𝑂(𝑚)timeusingBFS.∎
𝑓
𝑓
373F20 – Nisarg Shah 9
Level Graph
• Level graph 𝐿𝐺 of a directed graph 𝐺 = (𝑉, 𝐸):
➢ Level: l(𝑣) = length of shortest 𝑠 → 𝑣 path
➢Level graph 𝐿 = (𝑉,𝐸 ) is a subgraph of 𝐺 where we 𝐺𝐿
only retain edges 𝑢, 𝑣 ∈ 𝐸 where l 𝑣 = l 𝑢 + 1 o Intuition: Keep only the edges useful for shortest paths
373F20 – Nisarg Shah 10
Level Graph
• Level graph 𝐿𝐺 of a directed graph 𝐺 = (𝑉, 𝐸):
➢ Level: l(𝑣) = length of shortest 𝑠 → 𝑣 path
➢Level graph 𝐿 = (𝑉,𝐸 ) is a subgraph of 𝐺 where we 𝐺𝐿
only retain edges 𝑢, 𝑣 ∈ 𝐸 where l 𝑣 = l 𝑢 + 1 o Intuition: Keep only the edges useful for shortest paths
• Property: 𝑃 is a shortest 𝑠 → 𝑣 path in 𝐺 if and only if 𝑃 is an 𝑠 → 𝑣 path in 𝐿𝐺.
373F20 – Nisarg Shah 11
Edmonds-Karp Proof
• Lemma 1:
➢ Length of the shortest 𝑠 → 𝑡 path in 𝐺 never decreases.
𝑓
➢ Let 𝑓 and 𝑓′ be flows before and after an augmentation
• Proof:
step, and 𝐺 and 𝐺 ′ be their residual graphs.
𝑓
Residual graph 𝐺
𝑓 𝑓𝑓
Residual graph 𝐺 ′
373F20 – Nisarg Shah 12
Edmonds-Karp Proof
• Lemma 1:
➢ Length of the shortest 𝑠 → 𝑡 path in 𝐺
NOT IN SYLLABUS
never decreases. ➢ Let 𝑓 and 𝑓′ be flows before and after an augmentation
• Proof:
step, and 𝐺 and 𝐺 ′ be their residual graphs.
𝑓
➢ Augmentation happens along a path in 𝐿𝐺𝑓
𝑓
➢ For each edge on the path, we either remove it, add an opposite direction edge, or both.
➢ Opposite direction edges can’t help reduce the length of the shortest 𝑠 → 𝑡 path (exercise!).
➢ QED!
𝑓
373F20 – Nisarg Shah 13
Edmonds-Karp Proof
NOT IN SYLLABUS
• Lemma 2:
➢ After at most 𝑚 augmentations, the length of the
shortest 𝑠 → 𝑡 path in 𝐺 must strictly increase. 𝑓
• Proof:
➢ In each augmentation step, we remove at least one edge
from 𝐿𝐺𝑓
o Because we make the flow on at least one edge on the shortest
path equal to its capacity
➢ No new edges are added in 𝐿𝐺𝑓 unless the length of the
shortest 𝑠 → 𝑡 path strictly increases
➢ This cannot happen more than 𝑚 times! ∎
373F20 – Nisarg Shah 14
Edmonds-Karp Proof Overview
• Overview
➢ Lemma 1: The length of the shortest 𝑠 → 𝑡 path in 𝐺
never decreases.
➢ Lemma 2: After at most 𝑚 augmentations, the length of
the shortest 𝑠 → 𝑡 path in 𝐺 must strictly increase. 𝑓
➢ Theorem: The algorithm takes 𝑂(𝑚2𝑛) time.
𝑓
373F20 – Nisarg Shah 15
Edmonds-Karp Proof Overview
• Note:
➢ Some graphs require Ω(𝑚𝑛) augmentation steps
➢ But we may be able to reduce the time to run each augmentation step
• Two algorithms use this idea to reduce run time
➢ Dinitz’s algorithm [1970] ⇒ 𝑂(𝑚𝑛2)
➢Sleator–Tarjanalgorithm [1983]⇒𝑂(𝑚𝑛log𝑛) o Using the dynamic trees data structure
373F20 – Nisarg Shah 16
Network Flow Applications
373F20 – Nisarg Shah 17
Rail network connecting Soviet Union with Eastern European countries (Tolstoǐ 1930s)
373F20 – Nisarg Shah 18
Rail network connecting Soviet Union with Eastern European countries (Tolstoǐ 1930s)
Min-cut
373F20 – Nisarg Shah 19
Integrality Theorem
• Before we look at applications, we need the following special property of the max-flow computed by Ford-Fulkerson and its variants
• Observation:
➢ If edge capacities are integers, then the max-flow computed by Ford-Fulkerson and its variants are also integral (i.e. the flow on each edge is an integer).
➢ Easy to check that each augmentation step preserves integral flow
373F20 – Nisarg Shah 20
Bipartite Matching
• Problem
➢ Given a bipartite graph 𝐺 = (𝑈 ∪ 𝑉, 𝐸), find a maximum
cardinality matching
• We do not know any efficient greedy or dynamic programming algorithm for this problem.
• But it can be reduced to max-flow.
373F20 – Nisarg Shah 21
Bipartite Matching
𝑈𝑉 𝑈𝑉
• Create a directed flow graph where we…
➢ Add a source node 𝑠 and target node 𝑡
➢ Add edges, all of capacity 1:
o 𝑠 → 𝑢 for each 𝑢 ∈ 𝑈, 𝑣 → 𝑡 for each 𝑣 ∈ 𝑉 o𝑢→𝑣foreach 𝑢,𝑣 ∈𝐸
373F20 – Nisarg Shah 22
Bipartite Matching
• Observation
➢ There is a 1-1 correspondence between matchings of size 𝑘 in the original graph and flows with value 𝑘 in the corresponding flow network.
• Proof: (matching ⇒ integral flow)
➢ Take a matching 𝑀 = 𝑢1, 𝑣1 , … , 𝑢𝑘, 𝑣𝑘 of size 𝑘
➢ Construct the corresponding unique flow 𝑓 where… 𝑀
o Edges 𝑠 → 𝑢𝑖 , 𝑢𝑖 → 𝑣𝑖 , and 𝑣𝑖 → 𝑡 have flow 1, for all 𝑖 = 1, … , 𝑘 o The rest of the edges have flow 0
➢ This flow has value 𝑘
373F20 – Nisarg Shah 23
Bipartite Matching
• Observation
➢ There is a 1-1 correspondence between matchings of size 𝑘 in the original graph and flows with value 𝑘 in the corresponding flow network.
• Proof: (integral flow ⇒ matching)
➢ Take any flow 𝑓 with value 𝑘
➢Thecorrespondinguniquematching𝑀 =setofedges
𝑓
o Since flow of 𝑘 comes out of 𝑠, unit flow must go to 𝑘 distinct
from 𝑈 to 𝑉 with a flow of 1
vertices in 𝑈
o From each such vertex in 𝑈, unit flow goes to a distinct vertex in 𝑉 o Uses integrality theorem
373F20 – Nisarg Shah 24
Bipartite Matching
• Perfect matching = flow with value 𝑛
➢where𝑛= 𝑈 = 𝑉
• Recall naïve Ford-Fulkerson running time:
➢ 𝑂((𝑚 + 𝑛) ⋅ 𝐶), where 𝐶 = sum of capacities of edges leaving 𝑠
➢ Q: What’s the runtime when used for bipartite matching? • Some variants are faster…
➢ Dinitz’s algorithm runs in time 𝑂 𝑚 𝑛 when all edge capacities are 1
373F20 – Nisarg Shah 25
Hall’s Marriage Theorem
• When does a bipartite graph have a perfect matching?
➢ Well, when the corresponding flow network has value 𝑛
➢ But can we interpret this condition in terms of edges of the original bipartite graph?
➢ For 𝑆 ⊆ 𝑈, let 𝑁 𝑆 ⊆ 𝑉 be the set of all nodes in 𝑉 adjacent to some node in 𝑆
• Observation:
➢ If 𝐺 has a perfect matching, 𝑁 𝑆 ≥ |𝑆| for each 𝑆 ⊆ 𝑈
➢ Because each node in 𝑆 must be matched to a distinct node in 𝑁(𝑆)
373F20 – Nisarg Shah 26
Hall’s Marriage Theorem
• We’ll consider a slightly different flow network, which is still equivalent to bipartite matching
➢ All 𝑈 → 𝑉 edges now have ∞ capacity
➢𝑠 → 𝑈 and 𝑉 → 𝑡 edges are still unit capacity
𝑈𝑉 𝑈𝑉 ∞
11
11 ∞
373F20 – Nisarg Shah 27
Hall’s Marriage Theorem
• Hall’s Theorem:
➢ 𝐺 has a perfect matching iff 𝑁 𝑆 ≥ |𝑆| for each 𝑆 ⊆ 𝑉
• Proof (reverse direction, via network flow): ➢ Suppose 𝐺 doesn’t have a perfect matching
➢ Hence, max-flow = min-cut < 𝑛
➢ Let (𝐴, 𝐵) be the min-cut
o Can’t have any 𝑈 → 𝑉 (∞ capacity edges)
o Has unit capacity edges 𝑠 → 𝑈 ∩ 𝐵 and 𝑉 ∩ 𝐴 → 𝑡
373F20 - Nisarg Shah 28
Hall’s Marriage Theorem
• Hall’s Theorem:
➢ 𝐺 has a perfect matching iff 𝑁 𝑆 ≥ |𝑆| for each 𝑆 ⊆ 𝑉
• Proof (reverse direction, via network flow): ➢ 𝑐𝑎𝑝 𝐴, 𝐵 = 𝑈 ∩ 𝐵 + 𝑉 ∩ 𝐴 < 𝑛 = 𝑈
➢So 𝑉∩𝐴 <|𝑈∩𝐴|
➢ But 𝑁 𝑈 ∩ 𝐴 ⊆ 𝑉 ∩ 𝐴 because the cut doesn’t include any
∞ edges
➢So 𝑁 𝑈∩𝐴 ≤ 𝑉∩𝐴 <|𝑈∩𝐴|.∎
373F20 - Nisarg Shah 29
Some Notes
• Runtime for bipartite perfect matching ➢ 1955: 𝑂(𝑚𝑛) → Ford-Fulkerson
➢ 1973: 𝑂 𝑚 𝑛 → blocking flow (Hopcroft-Karp, Karzanov)
➢ 2004: 𝑂 𝑛2.378 → fast matrix multiplication (Mucha– Sankowsi)
෨ 10Τ7
➢ 2013: 𝑂 𝑚 → electrical flow (Mądry)
➢ Best running time is still an open question
• Nonbipartite graphs
➢ Hall’s theorem → Tutte’s theorem
➢ 1965: 𝑂(𝑛4) → Blossom algorithm (Edmonds) ➢ 1980/1994: 𝑂 𝑚 𝑛 → Micali-Vazirani
373F20 - Nisarg Shah 30
Edge-Disjoint Paths
• Problem
➢ Given a directed graph 𝐺 = (𝑉, 𝐸), two nodes 𝑠 and 𝑡,
find the maximum number of edge-disjoint 𝑠 → 𝑡 paths
➢ Two 𝑠 → 𝑡 paths 𝑃 and 𝑃′ are edge-disjoint if they don’t share an edge
373F20 - Nisarg Shah 31
Edge-Disjoint Paths
• Application:
➢ Communication networks
• Max-flow formulation
➢ Assign unit capacity on all edges
373F20 - Nisarg Shah 32
Edge-Disjoint Paths
• Theorem:
➢ There is 1-1 correspondence between sets of 𝑘 edge-
disjoint 𝑠 → 𝑡 paths and integral flows of value 𝑘 • Proof (paths → flow)
➢Let 𝑃 ,...,𝑃 be a set of 𝑘 edge-disjoint 𝑠 → 𝑡 paths 1𝑘
➢ Define flow 𝑓 where 𝑓 𝑒 = 1 whenever 𝑒 ∈ 𝑃 for some
𝑖, and 0 otherwise
➢ Since paths are edge-disjoint, flow conservation and
capacity constraints are satisfied ➢ Unique integral flow of value 𝑘
𝑖
373F20 - Nisarg Shah 33
Edge-Disjoint Paths
• Theorem:
➢ There is 1-1 correspondence between 𝑘 edge-disjoint
𝑠 → 𝑡 paths and integral flows of value 𝑘
• Proof (flow → paths)
➢ Let 𝑓 be an integral flow of value 𝑘
➢ 𝑘 outgoing edges from 𝑠 have unit flow ➢ Pick one such edge (𝑠, 𝑢1)
o By flow conservation, 𝑢1 must have unit outgoing flow (which we haven’t used up yet).
o Pick such an edge and continue building a path until you hit 𝑡
➢ Repeat this for the other 𝑘 − 1 edges coming out of 𝑠 with unit flow. ∎
373F20 - Nisarg Shah 34
Edge-Disjoint Paths
• Maximum number of edge-disjoint 𝑠 → 𝑡 paths
➢ Equals max flow in this network
➢ By max-flow min-cut theorem, also equals minimum cut
➢ Exercise: minimum cut = minimum number of edges we need to delete to disconnect 𝑠 from 𝑡
o Hint: Show each direction separately (≤ and ≥)
373F20 - Nisarg Shah 35
Edge-Disjoint Paths
• Exercise!
➢ Show that to compute the maximum number of edge- disjoint 𝑠-𝑡 paths in an undirected graph, you can create a directed flow network by adding each undirected edge in both directions and setting all capacities to 1
• Menger’s Theorem
➢ In any directed/undirected graph, the maximum number of edge-disjoint (resp. vertex-disjoint) 𝑠 → 𝑡 paths equals the minimum number of edges (resp. vertices) whose removal disconnects 𝑠 and 𝑡
373F20 - Nisarg Shah 36
Multiple Sources/Sinks
• Problem
➢ Given a directed graph 𝐺 = (𝑉, 𝐸) with edge capacities
𝑐:𝐸 → N, sources 𝑠 ,...,𝑠 and sinks 𝑡 ,...,𝑡 , find the 1𝑘 1l
maximum total flow from sources to sinks.
373F20 - Nisarg Shah 37
Multiple Sources/Sinks
• Network flow formulation
➢ Add a new source 𝑠, edges from 𝑠 to each 𝑠𝑖 with ∞ capacity
➢ Add a new sink 𝑡, edges from each 𝑡 to 𝑡 with ∞ capacity 𝑗
➢ Find max-flow from 𝑠 to 𝑡
➢ Claim: 1 − 1 correspondence between flows in two networks
373F20 - Nisarg Shah 38
Circulation
• Input
➢ Directed graph 𝐺 = (𝑉, 𝐸) ➢ Edge capacities 𝑐 ∶ 𝐸 → N ➢ Node demands 𝑑 ∶ 𝑉 → Z
• Output
➢ Some circulation 𝑓 ∶ 𝐸 → N satisfying oForeach𝑒∈𝐸:0≤𝑓 𝑒 ≤𝑐(𝑒) oForeach𝑣∈𝑉:σ𝑒entering𝑣𝑓(𝑣)−σ𝑒leaving𝑣𝑓 𝑣 =𝑑(𝑣)
➢ Note that you need σ𝑣:𝑑 𝑣 >0 𝑑(𝑣) = σ𝑣:𝑑 𝑣 <0 −𝑑(𝑣) ➢ What are demands?
373F20 - Nisarg Shah 39
Circulation
• Demand at 𝑣 = amount of flow you need to take out at node 𝑣
➢ 𝑑 𝑣 > 0 : You need to take some flow out at 𝑣
o So there should be 𝑑(𝑣) more incoming flow than outgoing flow o “Demand node”
➢ 𝑑 𝑣 < 0 : You need to put some flow in at 𝑣
o So there should be 𝑑 𝑣 more outgoing flow than incoming flow o “Supply node”
➢ 𝑑 𝑣 = 0 : Node has flow conservation o Equal incoming and outgoing flows
o “Transshipment node”
373F20 - Nisarg Shah 40
Circulation
• Example
373F20 - Nisarg Shah 41
Circulation
• Network-flow formulation 𝐺′
➢ Add a new source 𝑠 and a new sink 𝑡
➢For each “supply” node 𝑣 with 𝑑 𝑣 with capacity −𝑑(𝑣)
➢ For each “demand” node 𝑣 with 𝑑 𝑣 (𝑣, 𝑡) with capacity 𝑑(𝑣)
< 0, add edge (𝑠,𝑣) > 0, add edge
• Claim: 𝐺 has a circulation iff 𝐺′ has max flow of value σ𝑣:𝑑 𝑣 >0 𝑑(𝑣) = σ𝑣:𝑑 𝑣 <0 −𝑑(𝑣)
373F20 - Nisarg Shah 42
Circulation
• Example
373F20 - Nisarg Shah 43
Circulation
• Example
373F20 - Nisarg Shah 44
Circulation with Lower Bounds
• Input
➢ Directed graph 𝐺 = (𝑉, 𝐸)
➢ Edge capacities 𝑐 ∶ 𝐸 → N and lower bounds l ∶ 𝐸 → N ➢ Node demands 𝑑 ∶ 𝑉 → Z
• Output
➢ Some circulation 𝑓 ∶ 𝐸 → N satisfying oForeach𝑒∈𝐸:l(𝑒)≤𝑓 𝑒 ≤𝑐(𝑒) oForeach𝑣∈𝑉:σ𝑒entering𝑣𝑓(𝑣)−σ𝑒leaving𝑣𝑓 𝑣 =𝑑(𝑣)
➢ Note that you still need σ𝑣:𝑑 𝑣 >0 𝑑(𝑣) = σ𝑣:𝑑 𝑣 <0 −𝑑(𝑣)
373F20 - Nisarg Shah 45
Circulation with Lower Bounds
• Transform to circulation without lower bounds ➢ Do the following operation to each edge
• Claim: Circulation in 𝐺 iff circulation in 𝐺′
➢ Proof sketch: 𝑓(𝑒) gives a valid circulation in 𝐺 iff 𝑓 𝑒 − l(𝑒) gives a valid circulation in 𝐺′
373F20 - Nisarg Shah 46
Survey Design
• Problem
➢ We want to design a survey about 𝑚 products
o We have one question in mind for each product
o Need to ask product 𝑗’s question to between 𝑝 and 𝑝′ consumers 𝑗𝑗
➢ There are a total of 𝑛 consumers
o Consumer 𝑖 owns a subset of products 𝑂𝑖
o We can ask consumer 𝑖 questions about only these products
o We want to ask consumer 𝑖 between 𝑐 and 𝑐′ questions 𝑖𝑖
➢ Is there a survey meeting all these requirements?
373F20 - Nisarg Shah 47
Survey Design
• Bipartite matching is a special case ➢ 𝑐 = 𝑐′ = 𝑝 = 𝑝′ = 1 for all 𝑖 and 𝑗
𝑖𝑖𝑗𝑗
• Formulate as circulation with lower bounds
➢ Create a network with special nodes 𝑠 and 𝑡
➢ Edge from 𝑠 to each consumer 𝑖 with flow ∈ [𝑐 , 𝑐′] 𝑖𝑖
➢ Edge from each consumer 𝑖 to each product 𝑗 ∈ 𝑂 with
flow ∈ [0,1]
➢Edge from each product 𝑗 to 𝑡 with flow ∈ [𝑝 ,𝑝′] 𝑗𝑗
➢Edge from 𝑡 to 𝑠 with flow in [0,∞] ➢ All demands and supplies are 0
𝑖
373F20 - Nisarg Shah 48
Survey Design
• Max-flow formulation:
➢ Feasible survey iff feasible circulation in this network
373F20 - Nisarg Shah 49
Image Segmentation
• Foreground/background segmentation
➢ Given an image, separate “foreground” from “background”
• Here’s the power of PowerPoint (or the lack thereof)
Remove background
373F20 - Nisarg Shah 50
Image Segmentation
• Foreground/background segmentation
➢ Given an image, separate “foreground” from “background”
• Here’s what remove.bg gets using AI
Remove background
373F20 - Nisarg Shah 51
Image Segmentation
• Informal problem
➢ Given an image (2D array of pixels), and likelihood estimates of different pixels being foreground/background, label each
pixel as foreground or background
➢ Want to prevent having too many neighboring pixels where one is labeled foreground but the other is labeled background
373F20 - Nisarg Shah 52
Image Segmentation
• Input
➢ An image (2D array of pixels)
➢ 𝑎𝑖 = likelihood of pixel 𝑖 being in foreground
➢ 𝑏𝑖 = likelihood of pixel 𝑖 being in background
➢ 𝑝𝑖,𝑗 = penalty for “separating” pixels 𝑖 and 𝑗 (i.e. labeling one of them as foreground and the other as background)
• Output
➢ Label each pixel as “foreground” or “background”
➢ Minimize “total penalty”
o Want it to be high if 𝑎𝑖 is high but 𝑖 is labeled background, 𝑏𝑖 is high but 𝑖 is labeled foreground, or 𝑝𝑖,𝑗 is high but 𝑖 and 𝑗 are separated
373F20 - Nisarg Shah 53
Image Segmentation
• Recall
➢ 𝑎𝑖 = likelihood of pixels 𝑖 being in foreground ➢ 𝑏𝑖 = likelihood of pixels 𝑖 being in background ➢ 𝑝𝑖,𝑗 = penalty for separating pixels 𝑖 and 𝑗
➢ Let 𝐸 = pairs of neighboring pixels
• Output
➢ Minimize total penalty
o 𝐴 = set of pixels labeled foreground o 𝐵 = set of pixels labeled background o Penalty =
𝑏+𝑎+ 𝑝
𝑖 𝑗 𝑖,𝑗
𝑖∈𝐴 𝑗∈𝐵 𝑖,𝑗 ∈𝐸 𝐴∩ 𝑖,𝑗 =1
373F20 - Nisarg Shah 54
Image Segmentation
• Formulate as a min-cut problem
➢ Want to divide the set of pixels 𝑉 into (𝐴, 𝐵) to minimize
𝑏+𝑎+ 𝑝
𝑖 𝑗 𝑖,𝑗
𝑖∈𝐴 𝑗∈𝐵 𝑖,𝑗 ∈𝐸 𝐴∩ 𝑖,𝑗 =1
➢ Nodes:
o source 𝑠, target 𝑡, and 𝑣𝑖 for each pixel 𝑖
➢ Edges:
o (𝑠, 𝑣𝑖 ) with capacity 𝑎𝑖 for all 𝑖 o (𝑣𝑖 , 𝑡) with capacity 𝑏𝑖 for all 𝑖
o (𝑣 , 𝑣 ) and (𝑣 , 𝑣 ) with capacity 𝑝 each for all neighboring (𝑖, 𝑗) 𝑖𝑗𝑗𝑖 𝑖,𝑗
373F20 - Nisarg Shah 55
Image Segmentation
• Formulate as min-cut problem ➢ Here’s what the network looks like
373F20 - Nisarg Shah 56
Image Segmentation
➢ Consider the min-cut (𝐴, 𝐵)
𝑐𝑎𝑝𝐴,𝐵 =𝑏+𝑎+ 𝑝
𝑖∈𝐴 𝑗∈𝐵 𝑖,𝑗 ∈𝐸 𝑖∈𝐴,𝑗∈𝐵
➢ Exactly what we want to minimize!
𝑖 𝑗 𝑖,𝑗
If 𝑖 and 𝑗 are labeled differently, it will add 𝑝𝑖,𝑗 exactly once
373F20 - Nisarg Shah 57
Image Segmentation
• GrabCut [Rother-Kolmogorov-Blake 2004]
373F20 - Nisarg Shah 58
Profit Maximization (Yeaa...!)
• Problem
➢ There are 𝑛 tasks
➢ Performing task 𝑖 generates a profit of 𝑝𝑖
o We allow 𝑝𝑖 < 0 (i.e. performing task 𝑖 may be costly)
➢ There is a set 𝐸 of precedence relations
o 𝑖, 𝑗 ∈ 𝐸 indicates that if we perform 𝑖, we must also perform 𝑗
• Goal
➢ Find a subset of tasks 𝑆 which, subject to the precedence constraints, maximizes 𝑝𝑟𝑜𝑓𝑖𝑡 𝑆 = σ𝑖∈𝑆 𝑝𝑖
373F20 - Nisarg Shah 59
Profit Maximization
• We can represent the input as a graph ➢ Nodes = tasks, node weights = profits,
➢ Edges = precedence constraints
➢ Goal: find a subset of nodes 𝑆 with highest total weight
s.t. if 𝑖 ∈ 𝑆 and
𝑖, 𝑗
3
∈ 𝐸, then 𝑗 ∈ 𝑆 as well -4
-3
-1
7
-2
-9
3
373F20 - Nisarg Shah 60
Profit Maximization
• Want to formulate as a min-cut ➢ Add source 𝑠 and target 𝑡
➢ min-cut (𝐴, 𝐵) ⇒ want desired solution to be 𝑆 = 𝐴 ∖ {𝑠} ➢ Goals:
o 𝑐𝑎𝑝(𝐴, 𝐵) should nicely relate to 𝑝𝑟𝑜𝑓𝑖𝑡(𝑆) o Precedence constraints must be respected
• “Hard” constraints are usually enforced using infinite capacity edges
• Construction:
➢ Add each 𝑖, 𝑗 ∈ 𝐸 with infinite capacity
➢ For each 𝑖:
oIf𝑝𝑖 >0,add(𝑠,𝑖)withcapacity𝑝𝑖 o If 𝑝𝑖 < 0, add (𝑖, 𝑡) with capacity −𝑝𝑖
373F20 - Nisarg Shah 61
Profit Maximization
3
-3
7
-1
3
-2
0
373F20 - Nisarg Shah 62
Profit Maximization
∞
3
-3
∞ ∞
3
∞
0
3
7
s
∞∞
7
-1
∞
3
1
2
t
3
∞
-2
373F20 - Nisarg Shah 63
Profit Maximization
∞
3
-3
∞ ∞
3
∞
0
3
7
s
∞∞
7
-1
∞
3
1
2
A possible cut
3
t
∞
-2
QUESTION: What is the capacity of this cut?
373F20 - Nisarg Shah 64
Profit Maximization
Exercise: Show that...
1. A finite capacity cut exists.
2. If 𝑐𝑎𝑝(𝐴, 𝐵) is finite, then 𝐴\ 𝑠 is a valid solution;
3. Minimizing 𝑐𝑎𝑝(𝐴, 𝐵) maximizes 𝑝𝑟𝑜𝑓𝑖𝑡(𝐴\ 𝑠 )
• Show that 𝑐𝑎𝑝 𝐴, 𝐵 = constant − 𝑝𝑟𝑜𝑓𝑖𝑡 𝐴\ 𝑠 , where the constant is independent of the choice of (𝐴, 𝐵)
373F20 - Nisarg Shah 65