Maximum Weighted
Matching Algorithm
Christina Witwer
Wien 2002
Institute for Theoretical Biochemistry
University of Vienna
Some Definitions(I)
A graph G consists of a set V of vertices (nodes) and
a set E of edges
G = (V, E)
A weighted graph has a weight wij assigned to each
edge [vi, vj ] E.
32
12
12
24
24
12
3
24
5
32
Matching: A subset M E of edges is called a matching, if each vertex is contained in no more than one
edge.
32
12
24
24
12
12
3
24
5
32
Some Definitions(II)
Maximum cardinality matching: contains the maximum number of edges of a graph that form a matching.
Maximum weighted matching: The sum of the weights
of the edges forming the matching is maximal.
Motivation
View a RNA-sequence with a list of possible basepairs
as a graph:
Nucleotides Vertices
Basepairs Edges
Sequence: GUCAUCGA
V = {1, 2, 3, 4, 5, 6, 7, 8}
Possible basepairs:
E = {(1, 3), (1, 5), (1, 6), (2, 4), (2, 7), (2, 8), (3, 7), (5, 7), (5, 8)}
G1
A8
G1
A8
U2
G7
C3
C6
U2
G7
C3
C6
A4
A4
U5
U5
U
A
Some Definitions(III)
Alternating path with respect to a matching M: Ordered list of vertices, so that
each vertex is contained only once
the edges connecting the vertices are alternately
in M and not in M.
1
5
2
6
Some Definitions(IV)
Augmenting path with respect to a matching M: An
alternating path that starts and ends with an unmatched edge.
Symmetric Difference: S1 S2 = (S1 S2) (S1 S2 )
M = {(2, 4), (3, 5)}
P = {(1, 2), (2, 4), (4, 3), (3, 5), (5, 6)}
2
6
3
Augment: M 0 = M P
6
3
M 0 = {(1, 2), (4, 3), (5, 6)}
Berges Lemma: A matched graph (G, M) has an augmenting path if and only if M is not a maximum cardinality matching.
Sketch for an algorithm
k-Matching
search for an augmenting path
augment
(k+1)-Matching
If no more augmenting path exists, the matching is
maximum
Maximum Cardinality Matching
Search for an augmenting path
Initially all unmatched vertices of the graph are labeled even (+), all matched vertices are unlabeled (*).
Starting with an unmatched vertex r + a tree T is
grown.
Let v
/ T be adjacent to any vertex u+ T . T is
extended by taking the unmatched edge uv and the
matched edge vw to T . v is labeled odd (-) and w is
labeled even (+).
Grow step
+ v*
*
w
When an even vertex u+
/ T is adjacent to any vertex
u+ T , an augmenting path p = (v, u, . . . , r) with
respect to M has been found.
+
v
_
n
+
v
Blossoms
+
8
+
b
Shrink step: G0 = (V 0, E 0)
V 0 = (V \ B) {b}
E 0 = (V \ B) {ub : uv (B) and u 6 B}
+
r
b
4
3
More Definitions
(S) = {uv E : u S and v 6 S}
(S) = {uv E : u S and v S}
B
5
6
4
8
1
3
2
(S) = {(3, 7), (4, 6)}
(S) = {(1, 2), (2, 3), (3, 4), (4, 5), (1, 5)}
Blossoms can be nested
14
B2
B1
3
2
r
7
6
11
8
9
10
13
Each vertex is a (trivial) blossom.
B1 is a subblossom of B2.
B2 is a (non-trivial) surface blossom.
Search for an augmenting path (I)
3
r
7
5
10
11
grow step
3
r
7
5
grow steps
*
10
11
Search for an augmenting path (II)
3
r
+
5
10
11
shrink step
+
1
2(b)
grow steps
*
10
11
Search for an augmenting path (III)
2(b)
10
11
expand step
3
r
7
5
Augmenting path!
10
11
Algorithm: Search for an Augmenting Path
let r be the only vertex of T
while no edge uv with u+ T and v +
/ T exists {
if an edge uv with u+ T and v
/ T exists:
grow step
else if an edge uv with u+ T and v + T exists:
shrink step
else terminate,
T is abandoned since no augmenting path
for r exists
an edge uv with u+ T and v +
/ T exists
.
expand step augmenting path
Algorithm: Maximum Cardinality Matching
M : Abitrary matching in G
label all free vertices even, unlabel all matched vertices
for each vertex r in G {
if r is matched continue with an other vertex
search for an augmenting path
if an augmenting path has been found {
augment M 0 = M P
unlabel all vertices contained in T
delete all blossoms of T
destroy T
}
else T has been abandoned
continue with another vertex
}
M is a maximum cardinality matching
Linear programming
Primal Problem:
q
P
Maximize
cj xj
j=1
subject to
q
P
aij xj b(i)
for all
i = 1, . . . , p,
xj 0
for all
j = 1, . . . , q.
aij (i) cj
for all
j = 1, . . . , q,
(i) 0
for all
i = 1, . . . , p.
j=1
Dual Problem:
p
P
Minimize
b(i)(i)
1=1
subject to
p
P
i=1
Complementary Slackness Conditions: A pair (x, ) of
the primal and dual feasible solutions are optimal, if
they satisfy the following conditions:
"
#
q
P
(i) b(i)
aij xj = 0
for each
i = 1, . . . , p.
j=1
xj
p
P
i=1
aij (i) cj = 0
for each
j = 1, . . . , q.
Linear programming (Example)
Maximize 200x1 + 400x2
subject to 1/40x1 + 1/60x2 1
1/50x1 + 1/50x2 1
xi 0
i = 1, 2
x2
Feasible Region
x1
LP Formulation of MWM (I)
integer linear program:
P
Maximize
we xe
eE
subject to
xe 1
for all u V
xe {0, 1}
for all e E
e(u)
xe =
0
1
if
if
e 6 M
eM
24
28
32
28
28
24
5 28 6
20
16
24
9
we = w(u, v), xe = x(u, v)
w(r, 1) = 28, w(1, 2) = 32, . . .
x(1, 2) = 1, x(3, 4) = 1, xe = 0 for the other edges
eE
we xe = 60
ad LP Formulation of MWM(II)
Weighthed graph:
3
2
2
2
Optimal Solution of the integer linear program:
edge 1 2 2 3 3 4 4 5 1 5 P
we xe = 5
xe
1
0
0
1
0
eE
3
2
2
5
Optimal Solution of the linear programing relaxation:
edge 1 2 2 3 3 4 4 5 1 5
xe
0.5
0.5
0.5
0.5
0.5
eE
we xe = 6
LP Formulation of MWM(II)
integer linear program:
P
Maximize
we xe
eE
subject to
xe 1
for all u V
xe {0, 1}
for all e E
e(u)
linear programing relaxation:
P
Maximize
we xe
eE
subject to
xe 1
for all u V
xe 0
for all e E
e(u)
linear program:
P
Maximize
we xe
eE
subject to
xe 1
for all u V
e(u)
xe b|B|/2c
for all B O
e(B)
xe 0
for all e E
O = {B V : |B| is odd and |B| 3}
More Definitions
(S) = {uv E : u S and v 6 S}
(S) = {uv E : u S and v S}
B
5
6
4
8
1
3
2
(S) = {(3, 7), (4, 6)}
(S) = {(1, 2), (2, 3), (3, 4), (4, 5), (1, 5)}
Primal-Dual Method for MWM
Primal:
P
Maximize
wuv xuv
uvE
subject to
xuv 1
for all u V
uv(u)
xuv b|B|/2c
for all B O
xuv 0
for all uv E
uv(B)
Dual:
P
P
Minimize
yu +
b|B|/2czB
uV
BO
yu 0
subject to
yu + y v +
for all u V
zB
for all B O
zB
wuv
for all uv E
BO
uv(B)
Complementary Slackness Conditions:
xuv > 0 =
yu > 0 =
zB > 0 =
uv = 0
P
xuv = 1
for all uv E
for all u V
uv(u)
P
xuv = b|B|/2c for all B O
uv(B)
Reduced Cost: uv = yu + yv wuv +
BO
uv(B)
zB
Initial Solution
xe = 0 for each edge e E(M = )
yu = max{we /2 : e (u)} for each vertex u V
zB = 0 for each B O
Feasible Solution of the Primal:
P
(P 1)
xuv 1
uv(u)
P
(P 2)
xuv b|B|/2c
for all u V
for all B O
uv(B)
(P 3)
xuv
for all uv E
Feasible Solution of the Dual:
(D1)
yu
for all u V
(D2)
zB
for all B O
zB
wuv
for all uv E
(D3) yu + yv +
BO
uv(B)
Complementary Slackness Conditions:
(CS1) xuv > 0 =
(CS2)
(CS3)
yu > 0 =
zB > 0 =
uv(u)
P
uv(B)
uv
=0
for all uv E
xuv
=1
for all u V
xuv
= b|B|/2c for all B O
Reducing Violations of CS 2
CS 2: yu > 0 =
xuv = 1 for all u V
uv(u)
Let r be a vertex that violates CS 2
(i.e. r is unmatched and yr > 0.)
match r
or
adjust the dual solution (y, z) such that y = 0
Matching a free vertex r
Search for an augmenting path, but only use tight
P
edges (where uv = yu + yv wuv +
zB = 0).
BO
uv(B)
Otherwise CS 1 ( xuv > 0 = uv = 0 ) would be
violated.
case 1: found an augmenting path
augment
case 2: T is abandoned (no further thight edges are
incident to any vertex u+ T )
dual adjustment
Requirements to the Dual Adjustment
The dual solution (y, z) gets adjusted to (y 0, z 0) such
that
R1: the objective value (
uV
yu +
b|B|/2czB ) of the
BO
dual problem strictly decreases
R2: the solutions are still feasible to the Primal
R3: the solutions are still feasible to the Dual
R4: (CS1) and (CS3) remain true for (y 0, z 0)
R5: yr strictly decreases
Performing a Dual Adjustment
>0
yv0 = yv
yv0 = yv +
for all v + T,
for all v T,
yv0 = yv
for all v {|+}
/ T,
0 = z + 2
zB
B
0 = z 2
zB
B
for all B + T,
for all B T,
0 = z
zB
B
for all B {|+}
/ T,
zB is only adjusted when B is a non-trivial surface
blossom.
Satisfaction of the Requirements (I)
R1: the objective value (f =
uV
yu +
b|B|/2czB ) of
BO
the dual problem strictly decreases
f = f 0 f
v+ T :
fv+ =
v T :
fv =
B+ T :
fB + = |B|()+b|B|/2c(2) = |B|+(|B|1) =
B T :
fB = |B| + b|B|/2c(2) = |B| (|B| 1) =
n+ = n + 1
f = n+() + n() =
Satisfaction of the Requirements (II)
R2: the solutions are still feasible to the Primal
x is not altered
R3: the solutions are still feasible to the Dual
restrictions on the value of :
for all u+ T
(D1) : yu 0
yu
(D2) : zB 0
zB /2
for all B T
Satisfaction of the Requirements (III)
(D3) : uv = yu + yv wuv +
zB 0
BO
uv(B)
e = uv : u T or v T
Case 1: uv = yu + yv wuv 0 e
/ (B)
Case 1a: u+ T and v T :
yu0 = yu ,
yv0 = yv +
0 =
uv
uv
Case 1b: u+ T and v + T :
yu0 = yu ,
yv0 = yv
0 =
uv
uv 2
uv /2
Case 1c: u+ T and v {|+}
/ T:
yu0 = yu ,
yv0 = yv
0 =
uv
uv
uv
Case 1d: u T and v T :
yu0 = yu + ,
yv0 = yv +
0 =
uv
uv + 2
Case 1e: u T and v {|+}
/ T:
yu0 = yu + ,
0 =
uv
uv +
yv0 = yv
Satisfaction of the Requirements (IV)
(D3) : uv = yu + yv wuv +
zB 0
BO
uv(B)
e = uv : u T or v T
Case 2: e = uv (B)
Case 2a: B + T :
yu0 = yu ,
yv0 = yv ,
0 = z + 2
zB
B
0 =
uv
uv
Case 2b: B T :
yu0 = yu + ,
0 =
uv
uv
yv0 = yv + ,
0 = z 2
zB
B
Satisfaction of the Requirements (V)
R4: (CS1) and (CS3) remain true for (y 0, z 0)
(CS1): xuv > 0 uv = 0
0 =
uv
uv
(CS3) : zB > 0
xuv = b|B|/2c for all B O
uv(B)
R5: yr strictly decreases
r+ T
Satisfaction of the Requirements (Summary)
= min{1 , 2, 3, 4, }, where
1 = min {yu : u+ T }
uV
2 = min {uv : u+ T, v {|+}
/ T}
uvE
3 = min {uv /2 : u+ T, v + T }
uvE
4 = min {zB /2 : B T }
BO
Case = 1 : yu = 0, u+ T
an even length alternating path p from u to r exists:
match r by replacing M by M p
Case = 2 : the responsible edge e = uv becomes
tight and can be used to extend T
Case = 3 : the responsible edge e = uv becomes
tight and can be used to shrink a new blossom
Case = 4 : zB of B will drop to zero, B cannot
participate in another dual adjustment expand B
Expand step for an odd Blossom
3
r
Bj
3 *
r
4 *
+
Bj
MWM: Algorithm
Initial Solution:
let M be the empty matching
yu = max{we /2 : e E} for each vertex u G
label each vertex u g even
for each vertex r G {
if r is matched or yr = 0 continue
let Br be the only blossom of T
repeat {
if an vertex u+ T with yu = 0 exists {
let P be the alternating path from u to r
replace M by m P
else if an edge uv with u+ T and uv = 0
exists {
case v
/ T : grow step
+
case v T : shrink step
case v +
/ T : augment step
else if there exists an odd blossom B T
with zB = 0
expand step for B
else {
determine
perform dual adjustment
}
} until r is matched or yr = 0
}
Example (I)
Weighthed Graph:
24
28
32
28
28
24
5 28 6
20
16
24
9
node u 1
2
3
4
5
6
7
8
9
r
yu
16 16 14 14 14 14 10 10 12 14
After 4 searches:
+ 28
* 32
24
2 *
* 28
4 *
28
24
* 28
24
16
* 20
Example (II)
node u 1
2
3
4
5
6
7
8
9
r
yu
16 16 14 14 14 14 10 10 12 14
+ 28
* 32
24
2 *
* 28
4 *
28
24
* 28
* 20
16
24
starting the search with r + T
(r +, 1) = 2
no tight edges are incident to r + dual adjustment
1 = 14, 2 = 2, 3 = , 4 =
=2
Example(III)
yv0 = yv for all v + T
T = {r +}
=2
2
3
4
5
6
7
8
9
r
node u 1
yu
16 16 14 14 14 14 10 10 12 14
0
yu
16 16 14 14 14 14 10 10 12 12
edge (r, 1) becomes tight grow step
+ 28
32
24
* 28
2 +
4*
28
24
* 28
* 20
16
24
(2+, 3) = 6, (2+, 5) = 6
no tight edges are incident to 2+ dual adjustment
1 = 12, 2 = 6, 3 = , 4 =
=6
Example (IV)
yv0 = yv for all v + T
yv0 = yv + for all v T
T = {r +, 1 , 2+}
=6
node u 1
2
3
4
5
6
7
8
9
r
yu
16 16 14 14 14 14 10 10 12 12
yu0
22 10 14 14 14 14 10 10 12 6
edge (2+, 3) becomes tight grow step
edge (2+, 5) becomes tight grow step
28
r
+ 28
32
24
2 +
28
24
28
24
7
16
* 20
Example (V)
2
3
4
5
6
7
8
9 r
node u 1
yu
22 10 14 14 14 14 10 10 12 6
edge (4+, 6+) is thight shrink step
B(2)
+ 28
r
+ 28
32
24
2 +
28
24
+ 28
+
6
* 20
16
24
(5+, 9+) = 2, (6+, 7) = 8
no tight edges are incident to (B(2))+ dual adjustment
1 = 6, 2 = 2, 3 = , 4 =
=2
Example (VI)
yv0 = yv for all v + T
yv0 = yv + for all v T
=2
node u 1
2
3
4
5
6
7
8
9 r
yu
22 10 14 14 14 14 10 10 12 6
0
24 8 12 12 12 12 10 10 12 4
yu
0 = z + 2 for all B + T
zB
B
zB (B(2)) = 4
edge (5+, 9+) is thight, 9+
/ T augment step
B(2)
+ 28
r
+ 28
32
24
2 +
28
24
+ 28
+
6
* 20
16
24
expand the blossom and find the even length alternating path from vertex 5 to r:
Example (VII)
28
24
28
32
20
28
28
24
16
24
wuv xuv = 108
wuv xuv = 124
uvE
augment
28
24
28
32
20
28
24
28
16
24
uvE
