The HopcroftKarp class represents a data type for computing a Maximum (cardinality) matching and a Minimum (cardinality) vertex cover in a bipartite graph. A Bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A Matching in a graph is a subset of its edges with no common vertices. A Maximum matching is a matching with the maximum number of edges.

A Perfect matching is a matching which matches all vertices in the graph. A Vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A Minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any biparite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover. The maximum matching problem in Nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

This implementation uses the Hopcroft-Karp algorithm. The order of growth of the running time in the worst case is (E + V) sqrt(V), where E is the number of edges and V is the number of vertices in the graph. It uses extra space (not including the graph) proportional to V.

See also , which solves the problem in O(E V) time using the Alternating path algorithm and BipartiteMatchingToMaxflow, which solves the problem in O(E V) time via a reduction to the maxflow problem.