Hopcroft-Karp Algorithm for Maximum Matching

Introduction:

In a Bipartite graph, we can say that the matching is a type of set of edges that is chosen in such a way that one endpoint doesn't share more than one edge. We can also say that the matching of the maximum number of edges is known as maximum matching. If we have added any other edges to a maximum matching, then it is no longer matching. In a bipartite graph, there may be a chance of more than one maximum matching.

Let's discuss some terms which are related to this algorithm:

1. Free Node or Vertex:

In a matching M, there is a node that is not a part of the matching. We can call this node a free node. In the below graph, u2 and v2 are free. In the third graph, no vertex is free.

2. Matching and Not-Matching edges:

In the matching M, the edges which are the part of the machine, we can call those edges matching edges. The edges that are not a part of matching can be called Non-matching edges. In the below graph, the first graph contains all the non-matching edges; , (u0, v1), (u1, v0) and (u3, v3) are matching in the second graph, and others are not matching.

3. Alternating Paths:

In a given matching M, when a path is connected to both matching and not matching edges, then we can call that path an alternating path. We can also say that all the single-edge paths are known as alternating paths. In the below graph, u0-v1-u2 and u2-v1-u0-v2 are known as alternating paths.

4. Augmenting path:

In a given matching M, when an alternating path starts and ends from a free node, then we can call this path an augmenting path. We can also say that All the single-edge paths which are start and end with free vertices are augmenting paths.

We have to note one thing: the augmenting path always has one extra matching edge. In the Hopcroft Karp algorithm, if there is an existing augmenting path, then the matching M is not maximum there.

Hopcroft Karp Algorithm:

This algorithm is based on the below steps. These are as follows:

1. First, we have to initialize the maximum matching M as empty.
2. If there is an existing augmented path P, then we have to remove all the matching edges of P, and then we have to add all the not-matching edges of p to M.
3. Then we have to return M.

In the diagram below, we have implemented the above things.

Implementation of Hopcroft Karp algorithm:

Before implementing this algorithm, we have to note some points. These are as follows:

• First, we have to find the argument path.
• After finding the argument path, we need to add the argument path to the existing machine. Here, adding the path means we have to make the previous matching edges on this path not matching and previous not matching edges matching.

The main idea behind the Breadth First search is to find the argumented path. The BFS can divide the graph into layers of matching and not matching edges because the BFS can only traverse level by level. Then, we have to add a dummy vertex NIL, which is used to connect all vertices on the left side and all vertices on the right side. With the help of some of the below arrays, we can find the augmenting path. We have to initialize the Distance to NIL as infinite. If we start from a dummy vertex and come back to it using alternating paths of distinct vertices, then there must be an augmenting path.

The required arrays are as follows:

• pairU[]:

The size of this array is m+1. Here, m is the number of vertices on the left side of the Bipartite Graph. With the help of this array, we can store the pair of u on the right side if u is matched and if there is nothing mathed then it will be NIL .

• pairV[]:

The size of this array is n+1. Here, n represents the number of vertices on the right side of the Bipartite Graph. With the help of this array, we can store the pair of v on the left side if v is matched and NIL otherwise.

• dist[]:

The size of this array is m+1. Here, m represents the number of vertices on the left side of the Bipartite Graph. If u is not matching and INF (infinite), then we have to initialize the dist[] as 0. Also, we have to initialize the dist[] of NIL as INF.

After finding the augmenting path, we have to take the help of DFS (Depth First Search) to add augmenting paths to the current matching.

Let's understand the implementation of this algorithm with the help of the below programs.

Implementation in C++ 14:

Code:

Output:

Explanation:

In the above code, we have implemented the Hopcroft-Karp Algorithm to find the maximum matching with the help of C++.

Time complexity:

Here, the time complexity for this algorithm is O(V x E), where E is the number of Edges and V is the number of vertices.

Space complexity:

Here, the space complexity for this algorithm is O(V).