Given a bipartite graph
, find the maximum weighted bipartite matching.
This problem can be solved using Hungarian Algorithm with
time complexity by iteratively finding the augmenting path.
There is also an algorithm called KM Algorithm which can also solve the maximum weighted bipartite matching.
Suppose the vertices are separated to two sets
and
. We give node weights to each of them, namely
and
. KM algorithm states that if a subgraph
of
that satisfies the following properties:
(1)
(2) For any edge
where
and
,
where
is the weight of the corresponding edge in
.
(3)
contains a perfect matching.
Then
is equivalent to the maximum weighted bipartite matching of
.
[Prove Start]
For any bipartite matching
, if it is included in
, the weight must be the sum of all the node weights. If there is a matched edge in
but not in
, then we can immediately conclude that it's weight sum must be smaller than the total node weights of
(By properties (1) and (2)). Then we can see that if property (3) is satisfied, it is a maximum weighted bipartite matching. QED
[Prove Ends]
The algorithm is stated as follow:
(1) Assign
and
to ensure property (1) is satisfied.
(2) If
has perfect matching, done
(3) If (2) does not hold, we can always find a path
from
such that it both starts and ends with nodes in
.
(4) For any path
described in (3), we decrease node weights
with the nodes in
and increase
with nodes in
.
can be said to be "augmented".
[Prove]
Consider two vertices
and
,
Case 1:
unchanged
Case 2:
is unchanged
Case 3:
while
is not
Note that
is decreased. the edge
is more likely to be included in
to have prefect matching
Case 4:
is not in
while
is
Note that
is increased. By property (1) the edge
will not be included in
to have prefect matching
[/Prove]
(5) Reconstruct
and repeat from (1) again.
How to find
remains the last problem. We want to make sure the followings are satisfied after (4):
(i) Property 1 holds
(ii) At least one edge is included in
Therefore we would like to decrease an amount such that Case 3 is satisfied. We then choose
to proceed the algorithm.
Obviously the algorithm runs in
time. By memorizing the candidates for
(we call them "slack"), we can speed it up in
time.
