CSC373H Lecture 8
Dan Zingaro
November 7, 2016
Maximum Bipartite Matching
GivenundirectedgraphG=(V,E),amatchingisasubsetof edges M such that, for each vertex v, v is the endpoint of at most one edge in M
v ismatchedbyM ifv istheendpointofsomeedgeinM
A maximum matching is matching of maximum cardinality
We focus on bipartite graphs
Vertex set V can be partitioned into L ∪ R, where all edges in E go between L and R
We further assume that every vertex is the endpoint of at least one edge
Bipartite Matching: Example
Here is a bipartite graph. Find a matching of 2 edges. Find a (maximal) matching of 3 edges.
Reducing to Maximum Flow
We can try to solve the maximum-matching problem from scratch — there are good ways to do so
But, maximum-flow is a general technique that can be used to solve many problems, including maximum-matching
In particular, if we can reduce the maximum-matching problem to max-flow, then all we do is run max-flow to solve the problem
What does it mean to reduce to max-flow?
Reducing to Maximum Flow…
The goal is to create a flow network G′ so that matchings in G correspond to flows in G′
We want that G has a matching M with |M| edges iff G′ has a flow with value |M|
ThenallwedotofindamaximummatchinginG isfinda maximum flow in G′
. . . and we already know how to find a maximum flow!
Reducing to Maximum Flow…
Here’s how we can construct flow network G′ from bipartite graph G:
Add new source vertex s and sink vertex t to G′, along with all original vertices
ForeachundirectededgeinGfromu∈Ltov∈R,add directed edge (u,v) to G′
Also add to G′ edges from s to each vertex in L, and from each vertex in R to t
(G′ has 2 more vertices and |V| more edges than G)
Finally, give each edge in G′ a capacity of 1
Reducing to Maximum Flow: Example
Here’s the flow network for our earlier bipartite graph.
Proof of Reduction
LetG=(V,E)beabipartitegraphwithvertexpartition V=L∪R
Let G′ = (V′,E′) be its corresponding flow network
Call flow f integer-valued if it assigns integer flow to each
edge in E′
We will now prove the “if” and “only if” parts of the correspondence between matchings and flows
Proof of Reduction…
Part 1:
If M is a matching in G, then there is an integer-valued flow f in G′ withvalue|f|=|M|.
We’re given a matching with |M| edges, and we have to find a flow with value |M|
Here’s a flow that does that
If(u,v)∈M,thenf(s,u)=f(u,v)=f(v,t)=1
For all other edges e, f(e) is 0
Capacity and conservation constraints are satisfied
Andforeach(u,v)∈M,1unitofflowleavess,so|f|=|M|
Proof of Reduction…
Part 2:
If f is an integer-valued flow in G′, then there is a matching M in G with |M| = |f |.
We’re given a flow with value |f |, and we have to find a matching with |f | edges
Here’s a matching that does that
LetMbetheedges(u,v)whereu∈L,v∈R,andf(u,v)=1
We have to prove three things about M
Exactly one edge leaves each vertex u
Exactly one edge enters each vertex v
M actually has |f | edges!
Proof of Reduction…
Does exactly one edge leave u?
u has exactly one incoming edge, from s, and its capacity is 1 That 1 unit of flow leaves u on edge (u,v)
So, no more flow can leave u on any other edge
Therefore, there can be only one edge for which u is the tail
Proof of Reduction…
Does exactly one edge enter v?
v has exactly one outgoing edge, to t, and its capacity is 1
That 1 unit of flow enters v on edge (u,v)
So, no more flow can enter v on any other edge
Therefore, there can be only one edge for which v is the head
Proof of Reduction…
Does M have |f | edges?
Considercut(A,B)inG′,whereA={s}∪Land
B = {t} ∪ R
No edges enter A, so |f | is the total flow leaving A M consists of all edges carrying flow from A
Each of these edges in M carries 1 flow, so there must be |f | of them
Edge-Disjoint Paths
A set of paths is edge-disjoint if no two paths in the set share an edge
The paths can share vertices
GivendirectedgraphG=(V,E)withdistinguishedverticesa and b, the goal is to find the maximum number of edge-disjoint paths that go from a to b
Edge-Disjoint Paths: Example
v0
v1
v4
v5
v2
v3
v6
v7
What is the maximum number of edge-disjoint paths from v0 to v7? v2 to v6?
Edge-Disjoint Paths: Reduction
We can reduce this problem to max-flow
Define flow network G′ to have the same nodes and edges as
G, with s = a and t = b
Set the capacity of each edge to 1
Now, the required proof is that there are k edge-disjoint paths inG iffthereisaflowofvaluek inG′
Edge-Disjoint Paths: Proof
Part 1:
We must show that if there are k edge-disjoint paths from a to b in G, then there is a flow of value k in G′
Consider the flow in G′ with
f(e)=1foreachedgeethatisonanyofthepaths
f(e′)=0foranyedgee′ thatisnotonanyofthepaths
The flow has value k, as required
Edge-Disjoint Paths: Proof…
Part 2:
Ifthereisaflowf ofvaluek inG′,thentherearek
edge-disjoint paths from a to b in G
For any flow network with integer edge capacities, there is an
integer-valued flow of maximum value (prove this!)
As edge capacities are all 1, Each edge that carries flow must carry exactly 1 unit of flow
Sowecaninsteadthinkaboutinteger-valued,0-1flows…
Edge-Disjoint Paths: Proof…
ifthereisa0-1flowf ofvaluek inG′,thenthesetofedges carrying flow constitutes k edge-disjoint paths in G
The proof is by induction on the number of edges in f that carry flow
If there are 0 such edges, then |f | = 0. Nothing to prove
Otherwise, at least one edge carries flow. Therefore, there
must be an edge (s,u) that carries one unit of flow.
As u has 1 unit of flow entering, it must have 1 unit of flow
leaving on some edge (u,v)
But now v has 1 unit of flow entering, so it must have 1 unit
of flow leaving on edge (v, w)
We continue this process until one of two things happens: we reach t or we form a cycle
Edge-Disjoint Paths: Proof…
1. We reach t
We use the s → t path as 1 of the k required edge-disjoint
paths
Let f ′ be the flow obtained by decreasing the flow on the edges of this path to 0
|f′|=k−1,andithasfeweredgesthanf thatcarryflow
Applyingtheinductivehypothesistof′,wegetk−1
edge-disjoint paths
Adding the edge-disjoint path that we found, we have k disjoint paths, as required
Edge-Disjoint Paths: Proof…
2. We reach a node n that we have reached before
Consider the cycle of edges visited between the first and
second visit of n
Obtain flow f ′ from f by decreasing the flow of each edge on
this cycle to 0
This doesn’t change the flow value, but does decrease the number of edges that carry flow
By the inductive hypothesis, we get k edge-disjoint paths from f ′, as required