Matchings in Bipartite Graphs¶

Algorithm¶

In this algorithm, we start with an empty matching and keep enlarging it as long as there exists an augmenting path in the graph. It can be easily observed that the maximality of the final matching becomes evident in this case. To find an augmenting path, we proceed as follows:

Suppose our graph consists of two parts with \(n_1\) vertices and \(n_2\) vertices. For each \(v = 1 ... n_1\) in the current graph, we search for an augmenting path. In the \(i\)-th phase, it can be claimed that the matching between the first \(i\) vertices of the first partition and the remaining vertices of the second partition is maximal. Consequently, the final matching will also be maximal. The implementation is as follows:

const int N = 2e3 + 5;
int n1, n2, m, k, match[N];
vector <int> adj[N];
bool mark[N];

bool try_kuhn(int u){
    mark[u] = true;
    for(auto v: adj[u])
        if(match[v] == -1 || (!mark[match[v]] && try_kuhn(match[v]))){
            match[v] = u;
            return true;
        }
    return false;
}

void read_input(){
    cin >> n1 >> n2 >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        adj[--u].push_back(--v);
    }
}

void calc(){
    memset(match, -1, sizeof match);
    for(int u = 0; u < n1; u++){
        memset(mark, false, sizeof mark);
        k += try_kuhn(u);
    }
}

void write_output(){
    cout << k << endl;
    for(int u = 0; u < n2; u++)
        if (match[u] != -1)
            cout << match[u] + 1 << ' ' << u + 1 << endl;
}

int main() {
    read_input();
    calc();
    write_output();
    return 0;
}

In the mentioned algorithm, for each vertex in the upper section, \(O(m)\) steps are executed, thus its time complexity is \(O(nm)\). However, there is another implementation of this same algorithm whose speed is at least twice as fast as the aforementioned algorithm (Why?):

const int N = 2e3 + 5;
int n1, n2, m, k, match[N];
vector <int> adj[N];
bool mark[N];

bool try_kuhn(int u){
    mark[u] = true;
    for(auto v: adj[u])
        if (match[v] == -1 || (!mark[match[v]] && try_kuhn(match[v]))) {
            match[v] = u;
            return true;
        }
    return false;
}

void read_input(){
    cin >> n1 >> n2 >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        adj[--u].push_back(--v);
    }
}

void calc(){
    memset(match, -1, sizeof match);
    while(true){
        bool flag = false;
        memset(mark, false, sizeof mark);
        for(int u = 0; u < n1; u++)
            if (!mark[u])
                k += try_kuhn(u);
        if (!flag)
            break;
    }
}

void write_output(){
    cout << k << endl;
    for (int u = 0; u < n2; u++)
        if (match[u] != -1)
            cout << match[u] + 1 << ' ' << u + 1 << endl;
}

int main(){
    read_input();
    calc();
    write_output();
    return 0;
}

Hall's Theorem¶

This theorem states another necessary and sufficient condition for a matching to be maximum in a bipartite graph. It was first proposed by Philip Hall and is known as the Marriage Theorem. The theorem is as follows:

Let \(X\) be a set of vertices in the first partition of a bipartite graph. The set \(X\) has a perfect matching in the graph if and only if for every subset of \(X\), say \(S\), and the set of their neighbors outside \(X\) in the graph, denoted \(T\), we have \(|S| \leq |T|\).

The necessity of this condition is obvious (otherwise, the number of adjacent vertices would be insufficient for matching). To prove sufficiency, we use contradiction: assume there exists a graph with this property that lacks a perfect matching.

Consider a maximum matching and an arbitrary unsaturated vertex \(u\) (which must exist!). Since this vertex is unmatched, we take an arbitrary adjacent matched vertex. By the problem's assumption, these two vertices have another adjacent vertex that is either unmatched (yielding an augmenting path) or matched, whose matched vertex we add to the set. Repeating this process, and since the number of adjacent vertices to \(X\) is at least their own size, we eventually reach a stage where the current set has an adjacent unsaturated vertex. This creates an augmenting path, contradicting the maximality of our matching.

Matching in k-Regular Bipartite Graphs¶

According to Hall's theorem, it can be proven that a k-regular bipartite graph has a perfect matching. To prove this, it suffices to show that Hall's condition holds for it.

Consider a set of vertices \(S\) from the first partition of the graph and let \(T\) be their neighbors in the second partition. We prove that \(|S| \leq |T|\). We know the total number of edges between the two partitions is \(x = |S| \times k\). From this relation, we can conclude \(|T| \geq (x \div k) = |S|\).

Thus, Hall's condition is satisfied in our graph, and a perfect matching certainly exists in the graph.

Generalization of Hall's Theorem¶

We have a bipartite graph called \(G\) and want to remove some of its edges such that the degree of each vertex in the first partition like \(u\) becomes \(a_u\), and the degree of each vertex in the second partition becomes at most one. To solve this problem, we construct a graph \(G'\) such that it contains a perfect matching from the first partition to the second if and only if such an edge set exists in graph \(G\);

We construct graph \(G'\) by replacing each vertex \(u\) in the first partition with a set of \(a_u\) vertices (which are copies of vertex \(u\)). For each edge like \((u, v)\) in the original graph, we connect all vertices in the copy set of \(u\) to vertex \(v\). The resulting graph is bipartite (Why?). If Hall's condition holds (i.e., it has a perfect matching), then for each edge between the copy set of vertex \(u\) and vertex \(v\) in \(G'\), we keep the edge \((u, v)\) in \(G\), which clearly gives us the desired edge set. If \(G'\) has no perfect matching, we can similarly conclude that no such edge set exists in \(G\) (by reversing the argument).

Consider the process of checking Hall's condition in graph \(G^{\prime}\). For every subset \(S\) from the first partition of \(G^{\prime}\) and its neighbor set \(T\), we verify that \(|S| \leq |T|\). Note that if some copies of \(u\) are included in \(S\) but not all, we can add all copies to \(S\) without changing \(T\) - this only increases \(S\). Therefore, we only need to check subsets \(S\) where either all copies of each \(u\) are included or none are.

After careful consideration, we conclude that the above reasoning leads to the following necessary and sufficient condition for graph \(G\):

Where \(S\) is any subset of vertices in the first partition of the graph, and \(T\) is the union of neighbors of \(S\).