The BipartiteMatching 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 Alternating path algorithm. It is equivalent to reducing to the maximum flow problem and running the augmenting path algorithm on the resulting flow network, but it does so with less overhead. The order of growth of the running time in the worst case is (E + V) 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 sqrt(V)) using the Hopcroft-Karp algorithm and BipartiteMatchingToMaxflow, which solves the problem in O(E V) time via a reduction to maxflow.