Graph algorithms - Maximum matching in a bipartite graph

Problem: given a bipartite undirected graph, find a set of edges, of maximum size, that has the property that no two edges have an endpoint in common.

Note: a bipartite graph is a graph where the set of vertices is split into two subsets, with no edges having both endpoints in the same subset.

Practical problem modelled with the above: we have a set of workers (left set of vertices) to be assigned to some working positions (right vertices). Each worker may be qualified only for some of the working positions (qualifications are represented by the edges). Each worker can be assigned to at most one working position, and at most one worker can be assigned to a working position (no two selected edges may have an endpoint in common). Assign a maximum number of workers to working positions.

Example: find the maximum matching in the graph below:

Solution: The naive approach would be to select edges until no more edges are available without having an endpoint in common with an already selected edge. This naive greedy solution may get stuck in a local maximum. For the above example, 1-A, 2-B, 3-C is maximal (cannot be extended) but not maximum (one can find a larger set).

A better approach is to consider a transport graph associated to the matching problem, and maximize the flow in that graph.

Augmenting paths:
s-1-A-t
s-2-B-t
s-3-C-t
Residual graph after them:

Augmenting path: s-4-C-3-D-d.
Resulting residual graph:

Final match: 1-A, 2-B, 3-D, 4-C :

Problem: Edge cover in a bipartite graph: given a bipartite graph, find a minimum set of vertices such that each edge of the graph has at least one endpoint in that set.

Note: This problem, for a general undirected graph, is known to be NP-hard. In the case of a bipartite graph, it is much simpler.

First, we note that the size of the minimum cover must be larger than or equal to the size of the maximum matching. This happens because each edge in a matching must be covered by a distinct vertex.

The optimal solution can be created as follows: create the flow problem associated to the bipartite graph, find a maximum flow; finally, in the residual graph, select as part of the cover:

• the vertices in the right set that are accessible from the source in the residual graph;
• the vertices in the left set that are not accessible from the source in the residual graph.

It can be then shown that:

• each edge of the original graph is covered;
• each edge selected in the matching has at most one endpoint covered.