1. Introduction
A matching in a graph is a set of edges, no two of which share a vertex. Given a graph, it is a well-known problem to find a matching of maximum carnality. All these algorithms for maximum matching, by berge’s theorem in 1957 [1], are led to search for augmenting paths. In the case of bipartite graphs, it is easier to search for augmenting paths using of bread-first search. These algorithms require
steps. But in the non-bipartite case, the problem becomes even more difficult so that until 1965 only exponential algorithm for finding a maximum matching in general graphs were known. The reason was that one did not know how to deal with odd cycles (Blossoms) in alternating paths in the process of searching for augmenting paths. Edmonds [4] defined the key notion of blossoms and finessed this difficulty in non-bipartite graphs by “shrinking” blossom. The straightforward implementation of his approach led to an
algorithm for maximum matching in general graphs. After further improvement there are
or
algorithms [2] [3] for it.
In 1973 Hoperoft and Karp [5] proved the following fact. If one computes in one phase a maximal set of shortest augmenting paths, then
such phases would be sufficient. For the bipartite case they showed that a phase can be implemented by a breath-first search followed by a depth-first search. This led to an
implementation of one phase and hence to an
algorithm for maximum matching in bipartite graphs. The HK Algorithm for maximum matching in bipartite graphs [1] is still the most efficient known algorithm for the problem.
The success of Hopcroft and Karp algorithm in bipartite graphs has made many people attempt to extend it to non-bipartite case. In fact ,in their paper almost all the results are derived for general graphs. The specialization to the bipartite case occurs in computing in one phase a maximal set of shortest augmenting paths only.
In 1980 Mieali and Vijay Vazirani [6] stated a matching algorithm in pseudocode, claimed to have an
implementation of a phase in general graphs. Although their result led to a most efficient general graph maximum matching algorithm running time of
and is cited in many papers and also in some textbooks but no proof of correctness was available. Also the paper of Peterson and Loui [7] does not clarify the situation.
In this article a new approach to deal with the blossom is proved, which makes a phase can be implemented by a breath-first search followed by a depth-first search.
After summarizing basic theory of matched problem and introducing the HK algorithm in bipartite graph in Section 1, we discuss the obstacle to extend the HK algorithm to the non-bipartite case, that is blossom, in Section 2. The theoretical basis of the new approach is established in Section 3 and then we construct the new algorithm, which extend HK algorithm in bipartite graph to non-bipartite case in Section 4.
2. The Basic Theory and Contribution of Hopcroft and Karp
Let
be a finite undirected graph (without loops or multiple edges) having the vertex set
and the edge set
. An edge
incident with vertices u and v is written
. A path in G is a sequence of vertices and edges (without repeated vertices)
In which
(i = 0, 1, ∙∙∙, r). Two vertices
and
are called end-poinds of the path. Especially, when
, i.e. two end-poinds overlap then
Is a circuit.
Let
is called neighborhood of u.
A set
is a matching if no vertex is incident with more than one edge in M. A matching of maximum cardinality is called a maximum matching. We say the maximum matching is complete, or perfect when
and
. We make the following definitions relative to a matching M. Edges in M are called matched edges; the others are free. A vertex v is free if it is incident with no edge in M otherwise it is matched.
A path
is called M-alternating path if its edges are alternately in E-M and in M; i.e.
(1.1)
(1.2)
A path with odd length 2r + 1 (without repeated vertices) is called an M-augmenting path if its end vertices
and
are both free.
It is easy to result in the lemma by Equation (1.1) and Equation (1.2):
Lemma 1.1.
is a new matching and
.
And the following theorem is also well known.
Theorem 1.1. (Berge) M is not a maximum matching if and only if there is an augmenting path relative to M.
According to above theorems, the algorithm for finding the maximum matching in a graph boils down repeatedly to search for a augmenting path P relative to current matching M and augment current matching to
.
The contribution of Hopcroft and Karp is to compute in one phase a maximal set of shortest vertex-disjoint augmenting paths with a same length
and augment current matching to
and proved that the number of phases at most
.
Algorithm A: Maximum Matching Algorithm (Hopcroft and Karp).
1)
2) Let
be the length of a shortest M-augmenting path. Find a maximum set of paths
with the properties that:
a) For each i,
is an M-augmenting path and
;
b) The
are vertex-disjoint.
3)
; go to step 1.
Theorem 1.2. (Hopcroft and Karp). [5] If the cardinality of a maximum matching is S then Algorithm A constructs a maximum matching within
executions of step 1.
This way of describing the construction of a maximum matching suggests that we should concentrate on the efficient implementation of an entire phase (i.e., the execution of Step 1 in Algorithm A).
For the bipartite case,Hopcroft and Karp showed that a phase can be implemented by a breath-first search followed by a depth-first search,which has time complexity
. Hence, by theorem 1.2, the algorithm A has time complexity
.
3. Nonbipartite Matching: Blossoms
Unfortunately, in non-bipartite graphs, the lack of bipartite structure makes one might be fail of searching augmenting path by breath-first search in the execution of Step 1 in Algorithm A and this situation makes the task of implementing a phase far more difficult.
The problem remains how to deal with blossoms in computing in one phase a maximal set of shortest augmenting paths in non-bipartite case.
Definition 2.1. A odd circuit with
vertices having k matched edges is called a blossom.
In Figure 1 (the matched edge are drawn with heavy line, the free vretices are drawn with small cycle). The odd circuits,
are blossoms. The only vertex incident with no matched edges in the blossom is called basis of the blossom, as
and
.
The Hopkroft and Karp’s Algorithm [5] of implementation of step 1 of Algorithm A might fail when using it in the non-bipartite graph if which contains a blossom, because one alternating path at the basis of a blossom traverses this blossom and starts “folding” on itself, with a disastrous consequence .
Edmond’s method of dealing with blossoms are also not adequate for the task of finding shortest augmenting paths since by “shrinking” them, length information is completely lost.
We attempt to find a way to through the barrier of blossom keeping length information in finding augmenting paths and then extend the John E. Hopcroft and Richart M. Karp Algorithm (HK Algorithm) for maximum matchings in bipartite graphs to general graphs.
4. Equivalent Digraph
A digraph
is defined by a set
of elements called vertices, a set
of elements called directed edges or darts, and two relations of incidence. These associate each dart d, the one with a vertex
called its head and the other with a vertex
called its tail. A dart
incident with
,
is written
and
is called inverse of d.
For a vertex, the number of darts sharing the vertex as head is called the indegree of the vertex and the number of darts sharing it as tail is called its outdegree.
The in degree of v is denoted by
and its out degree is denoted by deg+(v).
A path in digraph
is a sequence of
darts,
(3.1)
Or
(3.2)
where
of
, not necessarily all distinct. It requires that the
, whenever
. The first and last vertices of path P, that is
and
, are called the tail
and head
of path P, respectively. The number r is called the length
of path P.
Is called inverse of path P, where
.
Consider two paths P and Q in
, if
, there is a path PQ, called the product of P and Q, formed by writing down the terms of P, in their order in P, and continuing with the terms of Q, in their order in Q. It is easy to verify that
and
,
,
.
One dart is a path with length 1. One path
is the product of r darts
, i.e.
.
We say that P is dart-simple if no dart repeated in it.
For a given graph G, we associate with each edge
of G two distinct elements
and
called the opposite darts on e. We form an equivalent digraph
of G from the given graph G.
and
A path in
is edge-simple if no two of its terms are darts on the same edge of G. Thus an edge-simple is necessarily dart-simple.
Let M be a matching in G. Edges in M and the darts on them are called matched. The other edges and darts on them are free. A path in
is M-alter- nating if its darts are alternately free and matched and the first dart is necessarily free.
Let
be M-alternating then
is free when i is even and
is matched when i is odd.
Lemma 3.1. Let
be a M-alternating path in equivalent digraph
of G from a free vertex
to another free vertex
. If P is edge-simple in
then the alternating path
is a M-augmenting path in G.
Proof: Each vertex in P is the head or tail of a matched dart, except
, but
, so if
then the matched darts, which incident with
, are on the same edge of G, because no two of matched edges share an vertex. This would conflict with that P is edge-simple. Then the vertices
in P are all distinct.
is a M-augmenting in G. We call a edge-simple path P a M-augmenting path, for simple.
Definition 3.1. Assume i is odd, t. is even and
, the M-alternating path
meet the condition that
. We call
a blossom and
in-dart,
out-dart of the blossom.
It is easy to see:
1)
are matched therefore
are free, because
are even.
2)
is also a blossom in
and
are in-dart and out-dart of it respectively.
The M-alternating path P from a free vertex v to a free vertex u is called shortest if P is of least carnality among these M-alternating paths.
Lemma 3.2. Let
be a shortest M-alternating path in
from a free vertex
to an another free vertex
(
) , then either P is a M-augmenting path or P pass though a blossom.
Proof: If P be not M-augmenting then there is
,
. Let t be as small as possible, so that
then
, but
share vertex
as their head, so
is necessarily free, because
is alternating. If
then
. We can obtain a shorter alternating path from
to
by deleting
from P. This is contradict with that P is shortest.
Can only be the case that
, because they share
as their tail. The
is a blossom and
is in-dart,
is out-dart of it. □
5. The Algorithm to Implement Step 1 of Algorithm A in General Graph
We construct a directed graph
(4.1)
from the equivalent digraph
of G, which exhibits conveniently all shortest M-augmenting paths in
.
Let
be the equivalent digraph of G. D is a set of darts. Define:
For
The construction continues until for the first time a set
is constructed so that there is a
and
is M-free. Then
For example, the
shown by Figure 2 (the direction of all darts as shown by the big arrow) is constructed from the equivalent digraph
of the graph G shown by Figure 1. Figure 2 exhibit all of the shortest M-alternating paths from free vertex to free vertex in Figure 1.
The following properties of
is easy to see:
1) Each path from a free vertex
to a free vertex
in
is a shortest M-alternating path with length 2I*+1.We call it regular M-alternating path in
2) If a M-alternating path
,
and
then
and
.
is also a regular M-alter- nating path in
.
3) Let
be the set all regular M-alternating paths in
then
,
and
, by (b).
4) If
then there is no augmenting path in
because there is only one M-alternating path P in
and
. In this case we remove the vertex
from
, and continue to construct.
Let
Then it’s a matter of finding out the shortest M-augmenting paths in
, i.e. to implement the step 1 in Algorithm A .
Let
and
is M-free. We construct a directed graph
(4.2)
which is set of all shortest M-alternating paths with length 2I* + 1 from a set
of M-free vertices to the free vertex
where
Case 1:
. In this case there is no augmenting path with V as a end- vertex.
Figure 2. Directed graph including shortest M-alternating paths.
Case 2:
. In this case there is at least one M-alternating path from a free vertex
(other than V) to V in
.
For example, Figure 3 is
constructed from Figure 3, in which,.
,
include two darts
and
.
include only one dart
called Cut-dart . General, if
is a only one of
we call
a cut-dart in
. If
is a cut-dart then all of the paths in
pass
.
Claim 4.1. Each path
, either P is a M-augmenting path or P pass through a blossom, by lemma 3.2.
Claim 4.2. If di is a cut-dart and there is a M-augmenting path in J(L0, v) then
is not a cut-dart.
Claim 4.3 Each path
is a M-augmenting path if there is no blossom in
.
Claim 4.4. Let P be a M-alternating path in
and
,
then
is in
and
;
therefore
, where
.
Claim 4.5. If
pass through a blossom and dart d is the in-dart (out-dart) of the blossom then
is also pass through a blossom and
is the in-dart (out-dart) of it.
A blossom will be broken if to remove the in-dart or out-dart from a path
, which traverse the blossom .
Following theorem is the basis of the Algorithm to implement step1 of algorithm A.
Theorem 4.0 Let P be a augmenting path in
and
,
d is a in-dart(out-dart) of a blossom in
and d isn’t a cut-dart then
or
can’t be broken after removing d.
Proof: If d is not on P then it can’t be broken after removing d. If pass through d is on P then
is on
and d is not on
. Therefore d isn’t a cut-dart and it is a in-dart(out-dart) of a blossom in
.
Algorithm A1. The algorithm to implement step 1 of Algorithm A
1) to construct
by (4.1). Let
2) If
then end
3) For a
to construct
by (4.2)
Figure 3. In-dart (1,2) being not cut-dart.
4) If
then remove
from
go to 1.
5) Get a M-alternating path P in
.
6) If P is edge-simple then get a M-augmenting path and remove P and
from
, go to 1.
7) P Traverse a blossom and d is in-dart of it: if d isn’t cut-dart then remove d else remove
from
, go to 3.
To remove such vertices or darts (as in algorithm A1) may render certain other vertices useless, in the sense that they cannot be in any M-alternating paths. These vertices and darts must also be deleted; for, these dead-ends will make searching for an augmenting path more complicate. Hence we need an algorithm which deletes these dead-ends.
This is achieved as follows:
B: Deletion algorithm
For
to 0 step −1
For each
if
then remove v from Di
For j = 0 to 2I*
For each
if
then remove v from Dj in
(Figure 3).
For example, to get a M-alternating path
in
(Figure 3). Dart
on P is a in-dart and isn’t a cut-dart To remove
from
The digraph after removing
from
is shown by Figure 4, to get a M-alternating path
in it,
is a in-dart and is a cut-dart. We remove out-dart
and get a M-augmenting path
in the result digraph.
The implementation of a phase consists of the construction of a digraph
, followed by an iteration which alternately finds an augmenting path and executes the deletion algorithm. The iteration stops when
. It is easy to see that each dart of
is examined once when
is first constructed, and once more if the
or
of that dart d is deleted.
The execution time of a phase is
, where m is the number of edges in G, and n is the number of vertices. Hence the execution time of the entire algorithm is
, where s is the carnality of a maximum matching.
If G has n vertices then
and
, so that the execution time is bounded by
.
6. Conclusion
In this paper an algorithm running time of
to implement step 1 of Algorithm A in general graph has been proved. Different from the way of “shrinking” blossoms, which need to store the shrinked blossoms, the removed darts don’t need to be stored when run this algorithm, because they can never be on any augmenting paths. The space complexity of this algorithm is also
. The proved algorithm is very easy to program. The Mieali and Vijay Vazirani [6] algorithm, by contrast, is quite elaborate and its pseudo code is extensive.