Maximum Matching in General Graphs

Maximum Matching in General Graphs

Ahmad Khayyat
Department of Electrical & Computer Engineering
ahmad.khayyat@ece.queensu.ca

Course Project
CISC 879 — Algorithms and Applications
Queen’s University

November 19, 2008

ECE @ Queen’s • Fall 2008 Ahmad Khayyat Maximum Matching in General Graphs • 1

Introduction Paths, Trees and Flowers Eﬃcient Implementation Reachability Approach Conclusion

Outline

1 Introduction

2 Paths, Trees and Flowers

3 Eﬃcient Implementation of Edmonds’ Algorithm

4 Reachability Problem Approach

5 Conclusion



Outline

1 Introduction
Terminology
Berge’s Theorem
Bipartite Matching




5 Conclusion



Terminology

Maximum Matching

G = (V, E) is a ﬁnite undirected graph: n = |V |, m = |E|.
A matching M in G, (G, M ), is a subset of its edges such
that no two meet the same vertex.
M is a maximum matching if no other matching in G
contains more edges than M .
A maximum matching is not necessarily unique.
Given (G, M ), a vertex is exposed if it meets no edge in M .

M



Terminology

Augmenting Paths

An alternating path in (G, M ) is a simple path whose edges
are alternately in M and not in M .
An augmenting path is an alternating path whose ends are
distinct exposed vertices.

v1 v2 v3 v1 v2 v3

v6 v5 v4 v6 v5 v4



Berge’s Theorem

Berge’s Theorem

Berge’s Theorem (1957)
A matched graph (G, M ) has an augmenting path if and only if M
is not maximum.

v1 v2 v3 v1 v2 v3

v6 v5 v4 v6 v5 v4
Unique?
An Exponential Algorithm:
Exhaustively search for an augmenting path starting from an
exposed vertex.



Bipartite Matching

Bipartite Graphs

A bipartite graph G = (A, B, E) is a graph whose vertices can
be divided into two disjoint sets A and B such that every
edge connects a vertex in A to one in B.
Equivalently, it is a graph with no odd cycles.

1 A

C 1 C

4 D A 4 D
2
2 E E
B 5
3 B 3
5



Bipartite Matching

Bipartite Graph Maximum Matching

for all v ∈ A, v is exposed do
Search for simple alternating paths starting at v
if path P ends at an exposed vertex u ∈ B then
O(nm) P is an augmenting path {Update M }
end if
end for
Current M is maximum {No more augmenting paths}
1 C

A 4 D
2
E
B 5
3



Bipartite Matching

Bipartite Graph Maximum Matching

for all v ∈ A, v is exposed do
if path P ends at an exposed vertex u ∈ B then
O(nm) P is an augmenting path {Update M }
end if
end for
1 C 1 C

A 4 D A 4 D
2 2
E E
B 5 B 5
3 3



Bipartite Matching

Non-Bipartite Matching

Problem: Odd cycles . . .

4 6
1 2 3
5

1 2 3

6 4
5



Outline

1 Introduction

Blossoms
The Algorithm



5 Conclusion



Blossoms

Blossoms
Blossoms
A blossom B in (G, M ) is an odd cycle with a unique exposed
vertex (the base) in M ∩ B.

4 6
1 2 3
5

1 2 3

6 4
5



Blossoms

Edmonds’ Blossoms Lemma

Blossoms Lemma
Let G and M be obtained by contracting a blossom B in (G, M )
to a single vertex.
The matching M of G is maximum iﬀ M is maximum in G .

4 6
1 2 3
5

1 2 B 6



Blossoms

Detecting Blossoms

Performing the alternating path search of the bipartite
matching algorithm (starting from an exposed vertex):
´ Label vertices at even distance from the root as “outer”;
´ Label vertices at odd distance from the root as “inner”.
If two outer vertices are found adjacent, we have a blossom.

I

O I O
4 6
1 2 3
5
O



The Algorithm

Edmonds’ Algorithm (1965)

for all v ∈ V , v is exposed do
O(n3 ) O(n2 )
Shrink any found blossoms
if path P ends at an exposed vertex then
P is an augmenting path {Update M }
else if no augmenting paths found then
Ignore v in future searches
end if
end for

Complexity: O(n4 )



The Algorithm

Example

|M | = 4

1 2 3 4

10 9 5 6

8 7



The Algorithm

Example

|M | = 4
O I O I
1 2 3 4

O
10 9 5 6 I

8 7
O



The Algorithm

Example

|M | = 4
O I O I
1 2 3 4

10 9 B1
O

8

B1 = 5, 6, 7



The Algorithm

Example

|M | = 4
O I O I
1 2 3 4

O
10 9 B1
O

8
I

B1 = 5, 6, 7



The Algorithm

Example

|M | = 4
O I O I
1 2 3 4

10 B2
I O

B1 = 5, 6, 7
B2 = B1 , 8, 9 = 5, 6, 7, 8, 9



The Algorithm

Example

|M | = 4

1 2 3 4

10 B2

B1 = 5, 6, 7
B2 = B1 , 8, 9 = 5, 6, 7, 8, 9



The Algorithm

Example

|M | = 4

1 2 3 4

10 9 B1

8

B1 = 5, 6, 7
B2 = B1 , 8, 9 = 5, 6, 7, 8, 9



The Algorithm

Example

|M | = 4 |M | = 5

1 2 3 4

10 9 5 6

8 7

B1 = 5, 6, 7
B2 = B1 , 8, 9 = 5, 6, 7, 8, 9



Outline

1 Introduction


Data Structures
The Algorithm
Performance


5 Conclusion



Data Structures

Three Arrays
u is an exposed vertex.
A vertex v is outer if there is a path P (v) = (v, v1 , . . . , u),
where vv1 ∈ M .

1 MATE: Speciﬁes a matching. An entry for each vertex:
´ vw ∈ M ⇒ MATE (v) = w and MATE (w) = v.
2 LABEL: Provides a type and a value:
LABEL(v) ≥ 0 → v is outer
LABEL(u) → start label, P (u) = (u)
1 ≤ LABEL(v) ≤ n → vertex label
n + 1 ≤ LABEL(v) ≤ n + 2m → edge label

3 START (v) = the ﬁrst non-outer vertex in P (v).



The Algorithm

Gabow’s Algorithm (1976)
for all u ∈ V, u is exposed do
while ∃ an edge xy, x is outer AND
no augmenting path found do
if y is exposed, y = u then
(y, x, . . . , u) is an augmenting path
else if y is outer then
Assign edge labels to P (x) and P (y)
else if MATE (y) is non-outer then
Assign a vertex label to MATE (y)
end if
end while
end for



The Algorithm

Gabow’s Algorithm (1976)
O(n) for all u ∈ V, u is exposed do
while ∃ an edge xy, x is outer AND
no augmenting path found do
O(1) if y is exposed, y = u then
O(n) (y, x, . . . , u) is an augmenting path
O(n) else if y is outer then
O(n) Assign edge labels to P (x) and P (y)
O(n) else if MATE (y) is non-outer then
O(1) Assign a vertex label to MATE (y)
end if
end while
end for

Complexity: O(n3 )



Performance

Experimental Performance

Using an implementation in Algol W on the IBM 360/165
Worst-case graphs:
´ Eﬃcient Implementation: run times proportional to n2.8 .
´ Edmond: run times proportional to n3.5 .
Random graphs: times one order of magnitude faster than
worst-case graphs.
Space used is 5n + 4m.



Outline

1 Introduction



Reachability and Graphs
The Algorithm

5 Conclusion




The Reachability Problem in Bipartite Graphs
Construction:
Bipartite graph + Matching → Directed graph
G = (A, B, E) + M → G = (V , E )
´ V = V ∪ {s, t}
´ ∀ xy ∈ M , x ∈ A, y ∈ B → (x, y) ∈ E e∈M ⇒e:A→B
´ ∀ xy ∈ M , x ∈ A, y ∈ B → (y, x) ∈ E
/ e∈M ⇒e:B→A
/
´ ∀ b ∈ B, b is exposed → add (s, b) to E
´ ∀ a ∈ A, a is exposed → add (a, t) to E

A1 B1 A1 B1
=⇒ t s

A2 B2 A2 B2




The Reachability Problem in Bipartite Graphs
Construction:
Bipartite graph + Matching → Directed graph
G = (A, B, E) + M → G = (V , E )
´ V = V ∪ {s, t}
´ ∀ xy ∈ M , x ∈ A, y ∈ B → (x, y) ∈ E e∈M ⇒e:A→B
´ ∀ xy ∈ M , x ∈ A, y ∈ B → (y, x) ∈ E
/ e∈M ⇒e:B→A
/
´ ∀ b ∈ B, b is exposed → add (s, b) to E
´ ∀ a ∈ A, a is exposed → add (a, t) to E

A1 B1 A1 B1
=⇒ t s

A2 B2 A2 B2

An augmenting path in G ⇔ A simple path from s to t in G .



The Reachability Problem in General Graphs
Construction

For each v ∈ V , we introduce two nodes vA and vB
V = {vA , vB |v ∈ V } ∪ {s, t} s, t ∈ V, s = t
/
e ∈ M ⇒ e : A → B, e∈M ⇒e:B→A
/
E = {(xA , yB ), (yA , xB ) | (x, y) ∈ M }
∪ {(xB , yA ), (yB , xA ) | (x, y) ∈ M }
/
∪ {(s, xB ) | x is exposed} ∪ {(xA , t) | x is exposed}
t
1 2 1A 2A 3A 4A
=⇒
1B 2B 3B 4B
4 3
s




The Reachability Problem in General Graphs
Strongly Simple Paths

A path P in G is strongly simple if:
P is simple.
vA ∈ P ⇒ vB ∈ P .
/
Theorem
There is an augmenting path in G if and only if there is a strongly
simple path from s to t in G .

t
1 2 1A 2A 3A 4A
=⇒
1B 2B 3B 4B
4 3
s




Solving the Reachability Problem
Solution: A strongly simple path from s to t in G :
Depth-First Search (DFS) for t starting at s.
DFS finds simple paths.
We need to find strongly simple paths only.
We use a Modified Depth-First Search (MDFS) algorithm.
Example:

t
1 2 1A 2A 3A 4A
=⇒
1B 2B 3B 4B
4 3
s



The Algorithm

Data Structures

Stack K
´ TOP(K): the last vertex added to the stack K.
´ Vertices in K form the current path.
´ In each step, the MDFS algorithm considers an edge
(TOP(K), v), v ∈ V .

List L(vA )
´ To get a strongly simple path, vA and vB cannot be in K
simultaneously (we may ignore a vertex, temporarily).
´ List L(vA ) keeps track of such vertices.



The Algorithm

Hopcroft and Karp Algorithm for Bipartite Graphs (1973)
Step 1: M ←φ
Step 2: Let l(M ) be the length of a shortest augmenting path of M
Find a maximal set of paths {Q1 , Q2 , . . . , Qt } such that:
2.1 For each i, Qi is an augmenting path of M , |Qi | = l(M ),
Qi are vertex-disjoint.
2.2 Halt if no such paths exists.
Step 3: M ← M ⊕ Q1 ⊕ Q2 ⊕ · · · ⊕ Qt ; Go to 1.

Hopcroft and Karp Theorem
If the cardinality of a maximum matching is s, then this algorithm
√
constructs a maximum matching within 2 s + 2 executions of
Step 2.

√
Step 2 complexity: O(m) ⇒ Overall complexity: O( nm)



The Algorithm
√
An O( nm) Algorithm for General Graphs

Blum describes an O(m) implementation of Step 2 for general
graphs, using a Modiﬁed Breadth-First Search (MBFS).
Blum’s Step 2 Algorithm:
Step 1: Using MBFS, compute G
Step 2: Using MDFS, compute a maximal set of strongly simple paths
from s to t in G .

Blum’s Theorm
A maximum matching in a general graph can be found in time
√
O( nm) and space O(m + n).



Outline

1 Introduction




5 Conclusion
Summary
Questions



Summary

Summary

O(n2.5 )
O(n4 ) O(n3 ) O(n2.5 ) O(n2.5 )

1965 1976 1980 1989 1990 1991
Ed

Ga

M

Va
Bl iran
Ga
ica

um i’s
m

z
bo

bo
on

li
w’

w
&
ds

s
Im

Va

Pr
pl

z

oo
ira
em

f
ni
en
t
at
io
n



Summary

References

Jack Edmonds
Paths, Trees, and Flowers
Canadian Journal of Mathematics, 17:449–467, 1965.
http://www.cs.berkeley.edu/~christos/classics/edmonds.ps

Harold N. Gabow
An Eﬃcient Implementation of Edmonds’ Algorithm for
Maximum Matching on Graphs
Journal of the ACM (JACM), 23(2):221–234, 1976.

Norbert Blum
A New Approach to Maximum Matching in General Graphs
Lecture Notes in Computer Science: Automata, Languages and Programming,
443::586–597, Springer Berlin / Heidelberg, 1990.



Summary

Thank You

Thank You!



Questions

Questions

???


Maximum Matching in General Graphs

Recommended

More Related Content

What's hot (20)

Viewers also liked (14)

Recently uploaded (20)

Maximum Matching in General Graphs