[go: up one dir, main page]
Scribd
Upload
119 views19 pages

Competitive Programming: Maximum Bipartite Matching

The document discusses maximum bipartite matching and algorithms to solve it, specifically reducing it to a maximum flow problem. It summarizes the Ford-Fulkerson algorithm and introduces a simplified version called Kuhn's algorithm. It then walks through an example matching problem, demonstrating how an augmenting path is found to increase the matching. Finally, it discusses representing the problem as an adjacency matrix and the overall time complexity of finding augmenting paths.

Uploaded by

Khalid Mosaad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
119 views19 pages

Competitive Programming: Maximum Bipartite Matching

The document discusses maximum bipartite matching and algorithms to solve it, specifically reducing it to a maximum flow problem. It summarizes the Ford-Fulkerson algorithm and introduces a simplified version called Kuhn's algorithm. It then walks through an example matching problem, demonstrating how an augmenting path is found to increase the matching. Finally, it discusses representing the problem as an adjacency matrix and the overall time complexity of finding augmenting paths.

Uploaded by

Khalid Mosaad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

P T H I N K F A ST S

Competitive Programming
From Problem 2 Solution in O(1)

Graph Theory
Maximum Bipartite Matching

Mostafa Saad Ibrahim


PhD Student @ Simon Fraser University
Recall: Reduction to Flow

◼ One way to solve this problem is to reduce to


maximum flow problem

Src: http://www.geeksforgeeks.org/maximum-bipartite-
matching/
Recall: Reduction to Flow

Src: http://www.geeksforgeeks.org/maximum-bipartite-
matching/
Recall: Ford-Fulkerson Algorithm

◼ While (augmenting path)


◼ Flow += path flow
Recall: Augmenting Path

◼ Augmenting = Increase
◼ Path From Source to Sink in residual network
◼ The updated network given previous paths
◼ Path Edges = Positive Capacities
◼ Flow p to push = Min Capacity on path
◼ p > 0 ⇒ We can increase flow
Today Algorithm

◼ A simplified Ford-Fulkerson Algorithm


◼ Called Kuhn’s algorithm
◼ Customize augmenting path for bipartite graph
◼ Simpler code...intuitive..easier to improve
◼ Notice, a bipartite graph has V/2 Flow
maximum, where each vertex matched to other
◼ Find path is O(E)
◼ Hence Same order: O(EV) for bipartite graph
Initial Matching
0 1 2 3 4
Flow = 3
(0, 6), (1, 5), (2, 8)

10 nodes => max possible flow = 5

Can we increase the flow?


E.g. Match one more vertex?
5 6 7 8 9

4 has only one connection to 8

Can we add it?

but 8 already connected! Can we rematch it with other


node?

Graph Src: http://www.dis.uniroma1.it/~sankowski/lecture2.pdf


canMatch(4)
4 has 1 choice only: 8 0 1 2 3 4
Try match 4-8
------------------
Remove 2 - 8 connection
Match 4 to 8
canMatch(4) = canMatch(2)?

5 6 7 8 9

0 1 2 3 4

5 6 7 8 9
canMatch(2)
2 has 4 choices: 6, 7, 8, 9
Try match 4-6 0 1 2 3 4
------------------
Remove 0 - 6 connection
Match 2 to 6
canMatch(2) = canMatch(0)?

5 6 7 8 9

0 1 2 3 4

5 6 7 8 9
canMatch(0)
0 has 2 choices: 5, 6
0 1 2 3 4
Try match 4-6
------------------
Remove 0 - 5 connection
Match 0 to 5
canMatch(0) = canMatch(1)?

5 6 7 8 9

0 1 2 3 4

5 6 7 8 9
canMatch(1)
1 has 2 choices: 5, 7
0 1 2 3 4
Try match 1-7
------------------
Available. Just add it

canMatch(1) = true
then originally
canMatch(4) = true

5 6 7 8 9

0 1 2 3 4

5 6 7 8 9
Augmenting path
Augmenting path: 0 1 2 3 4
4-8-2-6-0-5-1-7 =
Add 4-8 Cancel 8-2
Add 2-6 Cancel 6-0
Add 0-5 Cancel 5-1
Add 1-7

Odd length
5 6 7 8 9

Paths to Down
Originally unmatched

Paths to Up
Originally matched
First/Last node
Originally unmatched
Visited Node?

◼ canMatch(7)
◼ canMatch(5)
◼ CanMatch(2)
◼ CanMatch(4) = False
◼ CanMatch(11) = False
◼ Nothing more = False
◼ CanMatch(6)
◼ CanMatch(2) = Visited before = False
◼ If node can’t match, it will never match
◼ Then overall order of augmented path: O(E)
Code

◼ Build adjacency[m][n] with (i, j) = 1 if edge


from ith top node to jth bottom node
◼ E.g. matrix rows = top, cols = bottom
◼ Adjacency matrix 2 x 3 = represents 5 nodes
0 1
1 1 0

0 1 1

Matched Edges{ (0, 1) }, -1 = Not assigned

BottomAssign = ColAssign = {-1, 0, -1}


0 1 2 TopAssign = RowAssign = {1, -1}
Code
Code
Min Path Coverage in DAG

◼ Please revise this problem in max flow video


Readings

◼ Link 1
◼ Hopcroft–Karp Algorithm for O(E Sqrt(v))
‫ﺗﻢ ﺑﺤﻤﺪ ﷲ‬

‫ﻋﻠﻤﻜﻢ ﷲ ﻣﺎ ﯾﻨﻔﻌﻜﻢ‬

‫وﻧﻔﻌﻜﻢ ﺑﻤﺎ ﺗﻌﻠﻤﺘﻢ‬

‫وزادﻛﻢ ﻋﻠﻤﺎ ً‬

You might also like