Last week recap
• Max Flow Problem
Ø Ford-Fulkerson algorithm
o Complexity
o Polynomial-time algorithms (Edmonds-Karp) o Correctness
Ø Max-Flow Min-Cut Theorem Ø Integrality Theorem
2021-03-01 CSC373 Winter 2021 – Sam Toueg 1
Network Flow Some Applications
2021-03-01 CSC373 Winter 2021 – Sam Toueg 2
Rail network connecting Soviet Union with Eastern European countries (Tolstoǐ 1930s)
373F19 – Nisarg Shah & Karan Singh 3
Min-cut
Rail network connecting Soviet Union with Eastern European countries (Tolstoǐ 1930s)
4
Bipartite Matching
2021-03-01 CSC373 Winter 2021 – Sam Toueg 5
Matching
𝐺 = (𝑉, 𝐸): undirected graph
• Amatching𝑀in𝐺isasubsetofedgesof𝐺suchthat
no two edges share the same node
• Maximal matching: not a subset of another matching • Maximum matching: a matching of maximum size
2021-03-01 CSC373 Winter 2021 – Sam Toueg 6
Bipartite Graph
Bipartite graph: undirected graph 𝐺 = (𝑉, 𝐸) such that 1. 𝑉 is partitioned into two sets 𝑋 and 𝑌
Ø 𝑋 and 𝑌 may have different size
2. Everyedgein𝐸connectsanodein𝑋toanodein𝑌
So 𝐺 = [(𝑋, 𝑌), 𝐸]
𝑋𝑌 𝐴𝑎
𝐵𝑏
𝑐
𝐷𝑑
persons
jobs
𝐶 can do jobs 𝑎 or 𝑏 but cannot do 𝑐 or 𝑑
𝐶
2021-03-01
CSC373 Winter 2021 – Sam Toueg
9
Bipartite Graph
Bipartite graph: undirected graph 𝐺 = (𝑉, 𝐸) such that 1. 𝑉 is partitioned into two sets 𝑋 and 𝑌
Ø 𝑋 and 𝑌 may have different size
2. Everyedgein𝐸connectsanodein𝑋toanodein𝑌 So 𝐺 = [(𝑋, 𝑌), 𝐸]
From CSC263J:
Fact: undirected graph 𝐺 is bipartite ⟺ 𝐺 has no odd cycle
Fact: can determine if 𝐺 is bipartite in 𝑂(𝑚 + 𝑛) using BFS or DFS
2021-03-01 CSC373 Winter 2021 – Sam Toueg 10
Bipartite Matching Problem
• Problem
ØInput: bipartite graph 𝐺 = (𝑉, 𝐸) ØOutput: maximum matching of 𝐺
𝑋𝑌 𝐴𝑎
𝐵𝑏
𝑋𝑌𝑋𝑌 𝐴𝑎𝐴𝑎
𝐵𝑏𝐵𝑏
matching of size 3
𝐶
𝑐𝐶
𝑐𝐶𝑐 𝐷𝑑𝐷𝑑
𝐷𝑑
maximum matching maximal but not maximum!
2021-03-01 CSC373 Winter 2021 – Sam Toueg 11
Bipartite Matching Problem
• Problem
ØInput: bipartite graph 𝐺 = (𝑉, 𝐸) ØOutput: maximum matching of 𝐺
• Can solve this problem by reducing it to the Max Flow problem • How?
2021-03-01 CSC373 Winter 2021 – Sam Toueg 12
Solving Bipartite Matching Using Max Flow
Turn 𝐺 = [(𝑋,𝑌),𝐸] into a flow network F = 𝐺′,𝑠,𝑡,𝑐 as shown below:
𝐺 = [(𝑋, 𝑌), 𝐸] 𝑋𝑌
𝐴𝑎 𝐵𝑏
𝑐𝑒=1 for every edge 𝑒
F= 𝐺′,𝑠,𝑡,𝑐 𝑋𝑌
𝐴𝑎
𝐵𝑏 𝑠
𝐶 𝐷𝑑
𝐷𝑑
𝑐𝐶
𝑡 𝑐
2021-03-01
CSC373 Winter 2021 – Sam Toueg
13
Bipartite Matching Algorithm
BIPARTITE-MATCHING(𝐺): Input: 𝐺 = [ 𝑋, 𝑌 , 𝐸] construct flow network F from 𝐺 𝑂(𝑚 + 𝑛)
𝑓←MaxFlow(F) 𝑂 𝑚C𝐶 ,here𝐶=𝑛⇒𝑂(𝑚C𝑛)
𝑀← 𝑥,𝑦 𝑥∈𝑋,𝑦∈𝑌and𝑓 𝑥,𝑦 =1} 𝑂(𝑚)
return 𝑀
By the integrality theorem: the flow 𝑓 found by MaxFlow is an integer on each edge Since the capacity of each edge is 1: the integer flow 𝑓 is either 0 or 1 on each edge
• We will show that 𝑀 is a maximum matching of 𝐺
• Running time:
2021-03-01 CSC373 Winter 2021 – Sam Toueg 15
𝑂(𝑚 C 𝑛)
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F
Corollary: Maximum Matching in 𝐺 = Max Flow in F
F= 𝐺′,𝑠,𝑡,𝑐, 𝑐𝑒 =1forall
𝐴𝑎 𝐵 𝑏 edge𝑒 𝐵 𝑏
𝐴𝑎
𝐶
𝑠 𝑐𝐶
𝑡 𝑐
2021-03-01
CSC373 Winter 2021 – Sam Toueg
16
𝐷𝑑 𝐷𝑑
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F
Proof: (⟹) Given a matching 𝑀 in 𝐺 of size 𝑘,
construct an integral flow 𝑓 in F of value 𝑘 as follows:
𝑓8(𝑒)=T1 if𝑒isonthepath𝑠→𝑥→𝑦→𝑡and(𝑥,𝑦)∈𝑀 0 otherwise
• 𝑓8 satisfies capacity constraint because ∀𝑒 ∈ 𝐸, 𝑓8 𝑒 ≤ 1 = 𝑐 𝑒 • 𝑓8 satisfies flow conservation constraint because …
𝐴 𝑎 F= 𝐺′,𝑠,𝑡,𝑐, 𝐴 𝑎 𝑐𝑒 =1forall
𝐵 𝑏 edge𝑒 𝐵 𝑏 𝑠
𝑓
𝑀
𝐶
𝑐𝐶
𝑡 𝑐
2021-03-01
CSC373 Winter 2021 – Sam Toueg
18
𝐷𝑑 𝐷𝑑
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F Proof: (⟹) Given a matching 𝑀 in 𝐺 of size 𝑘,
construct an integral flow 𝑓 in F of value 𝑘 as follows: 𝑓8(𝑒)=T1 if𝑒isonthepath𝑠→𝑥→𝑦→𝑡and(𝑥,𝑦)∈𝑀
0 otherwise
• 𝑓8 satisfies capacity constraint because ∀𝑒 ∈ 𝐸, 𝑓8 𝑒 ≤ 1 = 𝑐 𝑒 • 𝑓8 satisfies flow conservation constraint because …
Possible violations of flow conservation for 𝑥 ∈ 𝑋: 𝑠𝑥 𝑠𝑥𝑦
Possible violations of flow conservation for y ∈ 𝑌:
𝑦𝑡𝑥𝑦𝑡 𝑥′
𝑦
𝑠𝑥
𝑦′
⇒ (𝑥, 𝑦) ∧ (𝑥, 𝑦′) ∈ 𝑀
⇒ (𝑥, 𝑦) ∧ (𝑥′, 𝑦) ∈ 𝑀
⇒ 𝑀 is not a matching!
⇒ 𝑀 is not a matching!
𝑦𝑡
𝑥
2021-03-01
CSC373 Winter 2021 – Sam Toueg
19
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F Proof: (⟸) Given an integral flow 𝑓 in F of value 𝑘,
construct a matching 𝑀@ in 𝐺 of size 𝑘 as follows:
• Since𝑓(𝑒)isanintegerforeach𝑒and𝑐 𝑒 =1,𝑓 𝑒 =1or0 •Let𝑀@= 𝑥,𝑦 𝑥∈𝑋,𝑦∈𝑌and𝑓𝑥,𝑦=1}
•
Claim: 𝑀@ is a matching in 𝐺 Suppose not:
𝑦 𝑥𝑦
𝑦′
𝑥 𝑥′
2021-03-01
CSC373 Winter 2021 – Sam Toueg 20
violation of matching
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F Proof: (⟸) Given an integral flow 𝑓 in F of value 𝑘,
construct a matching 𝑀@ in 𝐺 of size 𝑘 as follows:
• Since𝑓(𝑒)isanintegerforeach𝑒and𝑐 𝑒 =1,𝑓 𝑒 =1or0 •Let𝑀@= 𝑥,𝑦 𝑥∈𝑋,𝑦∈𝑌and𝑓𝑥,𝑦=1}
•
Claim: 𝑀@ is a matching in 𝐺 Suppose not:
1𝑦𝑥1 𝑥1𝑦′ 𝑥′1𝑦
violation of matching
2021-03-01 CSC373 Winter 2021 – Sam Toueg 21
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F Proof: (⟸) Given an integral flow 𝑓 in F of value 𝑘,
construct a matching 𝑀@ in 𝐺 of size 𝑘 as follows:
• Since𝑓(𝑒)isanintegerforeach𝑒and𝑐 𝑒 =1,𝑓 𝑒 =1or0 •Let𝑀@= 𝑥,𝑦 𝑥∈𝑋,𝑦∈𝑌and𝑓𝑥,𝑦=1}
•
Claim: 𝑀@ is a matching in 𝐺 Suppose not:
1𝑦𝑥1
𝑠 1 𝑥 1 𝑦′ 𝑥′ 1 𝑦 1 𝑡
Violation of flow conservation constraint
2021-03-01 CSC373 Winter 2021 – Sam Toueg 22
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F Proof: (⟸) Given an integral flow 𝑓 in F of value 𝑘,
construct a matching 𝑀@ in 𝐺 of size 𝑘 as follows:
• Since𝑓(𝑒)isanintegerforeach𝑒and𝑐 𝑒 =1,𝑓 𝑒 =1or0 •Let𝑀@= 𝑥,𝑦 𝑥∈𝑋,𝑦∈𝑌and𝑓𝑥,𝑦=1}
• Claim: 𝑀@ is a matching in 𝐺
• Claim:|𝑀@|=𝑣 𝑓 =𝑘
𝑆𝐴𝑎𝑇
consider the cut 𝑆, 𝑇
Ø 𝑆 = {𝑠} ∪ 𝑋, 𝑇 = {𝑡} ∪ 𝑌 Ø by Lemma 2 (of Max Flow):
𝑣𝑓 =𝑓ABC 𝑆 −𝑓DE(𝑆)
𝑣𝑓 =𝑓ABC 𝑆 −0
𝑣𝑓 =|𝑀@|
So:|𝑀@|=𝑣𝑓 =𝑘
2021-03-01 CSC373 Winter 2021 – Sam Toueg
𝑏 𝑠𝑡
𝐵 𝐶𝑐
𝐷𝑑
26
Bipartite Matching to Max Flow
Lemma: ∃ matching of size 𝑘 in 𝐺 ⟺ ∃ integral flow of value 𝑘 in F
Corollary: Maximum Matching in 𝐺 = Max Flow in F
⇒ BIPARTITE-MATCHING(𝐺) finds Maximum Matching in 𝐺
BIPARTITE-MATCHING(𝐺): Input: 𝐺 = [ 𝑋, 𝑌 , 𝐸] construct flow network F from 𝐺
𝑓 ← MaxFlow(F)
𝑀← 𝑥,𝑦 𝑥∈𝑋,𝑦∈𝑌and𝑓 𝑥,𝑦 =1} return 𝑀
2021-03-01 CSC373 Winter 2021 – Sam Toueg 27
Some Notes
• Bipartite graph matching
Ø1955: 𝑂(𝑚𝑛) → Ford-Fulkerson
Ø1973: 𝑂 𝑚 𝑛 → Hopcroft-Karp
Ø2004: 𝑂 𝑛F.HIJ → Mucha–Sankowsi
ØMany other algorithms, e.g., Mądry, Christiano et. Al., etc.. ØBest running time is still an open question
• Nonbipartite graph
Ø1965: 𝑂(𝑚𝑛F) → Edmonds Ø1980: 𝑂 𝑚 𝑛 → Micali-Vazirani
373F19 – Nisarg Shah & Karan Singh 28