Maximum Bipartite Matching

Prerequisites: Bipartite Graph, Graph Matching

Introduction

This article discusses the maximum matching problem in bipartite graphs \(G=(X,Y,E)\).

A typical example of bipartite matching in real life is pairing men and women. Suppose there are several men (\(X\)) and women (\(Y\)), each person can only be paired once, and the allowed pairings are limited by a given list (\(E\)). The task of the bipartite maximum matching algorithm is to find the maximum number of pairings under these constraints, so that as many people as possible are successfully paired.

Hint

This article assumes that a partition (coloring) of the vertex set \(V\) of the bipartite graph is known: \(V=X\cup Y\). If the partition of the vertex set \(V\) is not known in advance, it can be computed in \(O(|V|+|E|)\) time using the bipartite graph coloring algorithm.

Kuhn's Algorithm

Kuhn's algorithm is a direct application of Berge's Lemma. It is also part of the Hungarian algorithm.

Process

To find a maximum matching, the algorithm enumerates all vertices one by one, finds an augmenting path starting from it, and augments along it. Since augmenting paths always have odd length, in a bipartite graph, their endpoints must lie in the left and right parts respectively. This implies that we only need to consider augmenting paths starting from the left part.

To find augmenting paths, we can orient the bipartite graph according to the current matching \(M\). In an augmenting path (or any alternating path) starting from an unmatched left vertex, we can only go from a left vertex to a right vertex along a non-matching edge, and then from a right vertex to a left vertex along a matching edge. Therefore, we can direct all non-matching edges from left to right, and all matching edges from right to left. The problem of finding an augmenting path reduces to finding a simple path from some unmatched left vertex to some unmatched vertex in this directed graph. This problem can be easily solved by DFS or BFS in \(O(|E|)\) time.

(In the figure, dark vertices are matched, light vertices are unmatched, red edges are matching edges, black edges are non-matching edges, and arrows indicate the orientation corresponding to the current matching. As shown, the path \(1\rightarrow 8\rightarrow 3\rightarrow 11\rightarrow 6\rightarrow 12\) is an augmenting path relative to the current matching.)

At the start of the algorithm, all edges are directed from left to right. Each time an augmenting path is found, all edges along the path are reversed to indicate that their matching status has changed. When the algorithm ends, all edges directed to the left are matching edges.

Since at most \(O(|V|)\) left vertices need to be enumerated once each, the overall time complexity of the algorithm is \(O(|V||E|)\).

Optimizations

There are some simple techniques to optimize the constant factor of Kuhn's algorithm:

Kuhn's algorithm is based on Berge's Lemma, which does not require the left and right parts of the bipartite graph to be given in advance. Therefore, Kuhn's algorithm can run correctly even if the left and right parts are not explicitly divided, as long as the graph itself is bipartite. However, it is often more efficient to first color the bipartite graph to determine its left and right parts.
Since the time complexity of the Kuhn algorithm described above is actually \(O(|X||E|)\), we can choose the smaller of the two parts of the bipartite graph as the left part \(X\).
When searching for augmenting paths, the markers used to avoid repeated searches do not need to be cleared for each DFS. We can clear the markers before trying to find augmenting paths for all unmatched left vertices. In one such round of search, all edges are visited at most once, so the complexity is still \(O(|E|)\); however, multiple augmenting paths may be found in one round, so the total number of rounds \(k\) is at most \(|M|+1\), where \(M\) is the maximum matching. Correspondingly, the overall complexity of the algorithm is reduced to \(O(k|E|)\).
When searching for augmenting paths, prioritize unmatched right vertices, as this implies shorter augmenting paths.
Since Berge's Lemma does not require the initial matching to be empty, at the start of Kuhn's algorithm, we can randomly select some disjoint edges as the initial matching to reduce the number of subsequent searches. If optimization 3 is already applied, this optimization can be ignored.

Although the worst-case complexity is still \(O(|V||E|)\), a well-optimized Kuhn's algorithm is quite efficient. However, to avoid being forced into the worst-case complexity by specific data, it is necessary to randomly shuffle the order of edges or vertices before matching.

Reference Implementation

When implementing, there is no need to actually maintain the orientation; it is sufficient to maintain the matched vertex for each vertex.

Template Problem Library Checker - Matching on Bipartite Graph

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <tuple>
#include <vector>

std::mt19937_64 rng(
    static_cast<std::mt19937_64::result_type>(std::time(nullptr)));

struct BipartiteGraph {
  int n1, n2;                       // number of vertices in X and Y, resp.
  std::vector<std::vector<int>> g;  // edges from X to Y
  std::vector<int> ma, mb;  // matches from X to Y and from Y to X, resp.
  std::vector<bool> vis;    // visiting marks for DFS.

  BipartiteGraph(int n1, int n2)
      : n1(n1), n2(n2), g(n1), ma(n1, -1), mb(n2, -1) {}

  // Add an edge from u in X to v in Y.
  void add_edge(int u, int v) { g[u].emplace_back(v); }

  // Find an augmenting path starting at u.
  bool dfs(int u) {
    vis[u] = true;
    // Heuristic: find unsaturated vertices whenever possible.
    for (int v : g[u]) {
      if (mb[v] == -1) {
        ma[u] = v;
        mb[v] = u;
        return true;
      }
    }
    for (int v : g[u]) {
      if (!vis[mb[v]] && dfs(mb[v])) {
        ma[u] = v;
        mb[v] = u;
        return true;
      }
    }
    return false;
  }

  // Kuhn's maximum matching algorithm.
  std::vector<std::pair<int, int>> kuhn_maximum_matching() {
    // Randomly shuffle the edges.
    for (int u = 0; u < n1; ++u) {
      std::shuffle(g[u].begin(), g[u].end(), rng);
    }
    // Find a maximal set of vertex-disjoint augmenting paths in each round.
    while (true) {
      bool succ = false;
      vis.assign(n1, false);
      for (int u = 0; u < n1; ++u) {
        succ |= ma[u] == -1 && dfs(u);
      }
      if (!succ) break;
    }
    // Collect the matched pairs.
    std::vector<std::pair<int, int>> matches;
    matches.reserve(n1);
    for (int u = 0; u < n1; ++u) {
      if (ma[u] != -1) {
        matches.emplace_back(u, ma[u]);
      }
    }
    return matches;
  }
};

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int n1, n2, m;
  std::cin >> n1 >> n2 >> m;
  BipartiteGraph gr(n1, n2);
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    gr.add_edge(u, v);
  }
  auto res = gr.kuhn_maximum_matching();
  std::cout << res.size() << '\n';
  for (int i = 0; i < res.size(); ++i) {
    std::cout << res[i].first << ' ' << res[i].second << '\n';
  }
  return 0;
}

Hopcroft–Karp Algorithm

The Hopcroft–Karp algorithm further optimizes the process of finding augmenting paths in Kuhn's algorithm, reducing the total number of rounds to \(O(|V|^{1/2})\), thus achieving a time complexity of \(O(|V|^{1/2}|E|)\). This algorithm is actually a special case of Dinic's algorithm.

Process

The algorithm still searches for augmenting paths, but to complete the matching in fewer rounds, it adopts the following strategy in each round:

Direct matching edges from right to left, and non-matching edges from left to right.
Perform BFS from all unmatched left vertices in the directed graph, recording the layer number \(d(v)\) for each visited vertex, until an unmatched right vertex appears at some layer. If no unmatched right vertex is found by the end of BFS, the current matching is already maximum.
Perform DFS from each unmatched left vertex in turn, searching for augmenting paths and augmenting along them. During DFS, extend only along edges that satisfy strictly increasing layer numbers (i.e., \(d(v') = d(v) + 1\)), and only visit vertices that have not been visited in this round of DFS. In particular, DFS will not visit vertices that were not visited in the previous BFS step.

In network flow terms, step 2 constructs a level graph, and step 3 finds a blocking flow on the level graph. A level graph is one where every edge goes from one layer to the next; a blocking flow, in this context, refers to a maximal set of augmenting paths that are pairwise vertex-disjoint. The set of augmenting paths obtained in step 3 is necessarily maximal: if not, suppose there is a new augmenting path; then when its starting point was enumerated, such a path should have been found.

Compared to the previous Kuhn algorithm, the most crucial change in the Hopcroft–Karp algorithm is the addition of the level graph construction step before finding the blocking flow. Performing DFS based on the level graph restricts the algorithm to always follow shortest paths to each vertex. The benefit is that the lengths of augmenting paths found in different rounds of the algorithm are strictly increasing. Moreover, it can be proven that until the maximum matching is found, the length of augmenting paths increases at most \(3|M|^{1/2}\) times, where \(|M|\) is the size of the maximum matching. This bounds the total number of augmentation rounds to \(O(|M|^{1/2})\), yielding a time complexity of \(O(|M|^{1/2}|E|)\). Since \(2|M|\le |V|\), the time complexity can also be written as the looser upper bound \(O(|V|^{1/2}|E|)\).

Proof

First, note that the lengths of augmenting paths found by the algorithm are strictly increasing across different rounds.

Suppose in the current round of BFS, vertices extend \(\ell\) layers. Since all unmatched right vertices found in BFS are in the same layer, all augmenting paths found in this round of DFS have length \(\ell\). We need to prove that after augmenting along this set of augmenting paths \(\{P_i\}\), there will be no augmenting paths of length at most \(\ell\) in the reoriented directed graph.

Actually, if \(P\) is the shortest augmenting path relative to \(M\), and \(P'\) is an augmenting path relative to \(M\oplus P\), then \(|P'|\ge |P| + 2|P\cap P'|\) holds. This is because \(N=(M\oplus P)\oplus P'\) augments \(M\) twice, so similar to the proof of Berge's Lemma, we can show that the symmetric difference \(M\oplus N=P\oplus P'\) contains at least two vertex-disjoint augmenting paths \(P_1\) and \(P_2\) relative to \(M\). Due to the minimality of \(P\), we have

\[ 2|P|\le |P_1|+|P_2|\le |P\oplus P'| = |P| + |P'| - 2|P\cap P'|. \]

This implies \(|P'|\ge |P| + 2|P\cap P'|\). Therefore, if after adding the augmenting paths \(\{P_i\}\), a new augmenting path \(P'\) still has the same length, it must be vertex-disjoint from all of them, contradicting the maximality of \(\{P_i\}\). This contradiction shows that after augmenting the blocking flow, new augmenting paths must be strictly longer.

Finally, we need to show that the length of augmenting paths increases at most \(3|M|^{1/2}\) times.

Let \(p=\lfloor|M|^{1/2}\rfloor\). After the first \(p\) rounds, the remaining augmenting paths have length at least \(|M|^{1/2}\). Let the current matching be \(M_p\). Then, similar to the previous case, we can show that the graph \((V,M\oplus M_p)\) contains \(|M|-|M_p|\) vertex-disjoint augmenting paths relative to \(M_p\). Each augmenting path uses at least \(|M|^{1/2}/2\) matching edges from \(M\), so the total number of such paths is at most \(2|M|^{1/2}\), i.e., \(|M|-|M_p|\le 2|M|^{1/2}\). This means starting from \(M_p\), at most \(2|M|^{1/2}\) more augmentations can be performed, which also implies the algorithm runs at most \(2|M|^{1/2}\) more rounds. Thus, the length of augmenting paths increases at most \(3|M|^{1/2}\) times in total.

This is only an estimate of the worst-case complexity of the Hopcroft–Karp algorithm. In practice, on random graphs, the time complexity of Hopcroft–Karp is often \(O(|E|\log |V|)\) with high probability[^hk-comp-ref].

Optimization

When constructing the level graph, like in the general Dinic's algorithm, the Hopcroft–Karp algorithm terminates upon reaching an unmatched right vertex. However, for the bipartite matching problem alone, this is unnecessary. Moreover, because BFS terminates early, limiting the scope of subsequent DFS, the number of augmenting paths found per round may be limited, slowing down the overall matching efficiency. On some graphs, its efficiency may even be worse than an optimized Kuhn's algorithm. Therefore, a simple improvement is not to terminate BFS early, but to construct the level graph for all reachable vertices.

Correctness Proof

In the optimized algorithm, the augmenting paths in the blocking flow will no longer have the same length, so the previous complexity proof no longer holds. However, it can be shown that by constructing an auxiliary graph for each round of the algorithm, we can still establish that the length of the shortest augmenting path strictly increases, ensuring the worst-case complexity remains correct.

Let the bipartite graph be \(G=(X,Y,E)\) and the current matching be \(M\). Let \(W\subseteq Y\) be the set of unmatched right vertices reachable by BFS, and let \(d(y)\) be the length of the shortest augmenting path reaching \(y\in W\). Let \(d_\text{max} = \max_{y\in W}d(y)\). Then, for each \(y\in W\), we can add a new chain starting from \(y\) of length \(d_\text{max} - d(y)\), marking the new vertices alternately as left and right, and the new edges alternately as matching and non-matching. Let the resulting graph be \(G'=(X',Y',E')\) with matching \(M'\), where the shortest augmenting path has length \(d_\text{max}\). Then, there is a bijection between the augmenting paths relative to \(M\) in \(G\) that can be found along the level graph—i.e., the shortest augmenting paths reaching the corresponding vertices—and the globally shortest augmenting paths relative to \(M'\) in \(G'\). Therefore, finding a blocking flow in the level graph of \(G\) and augmenting is equivalent to finding a blocking flow in the level graph of \(G'\) and augmenting. According to the previous proof, after augmentation, there will be no augmenting paths of length \(d_\text{max}\) in \(G'\). Hence, there will also be no augmenting paths of length \(d_\text{min}=\min_{y\in W} d(y)\) in \(G\): such a path, via the newly extended alternating path, would correspond to an augmenting path of length \(d_\text{max}\) in \(G'\). This again yields the conclusion that the length of the shortest augmenting path strictly increases across different rounds of the algorithm. Therefore, the overall complexity remains \(O(|M|^{1/2}|E|)\).

Reference Implementation

Template Problem Library Checker - Matching on Bipartite Graph

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

struct BipartiteGraph {
  int n1, n2;                       // number of vertices in X and Y, resp.
  std::vector<std::vector<int>> g;  // edges from X to Y
  std::vector<int> ma, mb;  // matches from X to Y and from Y to X, resp.
  std::vector<int> dist;    // distance from unsaturated vertices in X.

  BipartiteGraph(int n1, int n2)
      : n1(n1), n2(n2), g(n1), ma(n1, -1), mb(n2, -1) {}

  // Add an edge from u in X to v in Y.
  void add_edge(int u, int v) { g[u].emplace_back(v); }

  // Build the level graph.
  bool bfs() {
    dist.assign(n1, -1);
    std::queue<int> q;
    for (int u = 0; u < n1; ++u) {
      if (ma[u] == -1) {
        dist[u] = 0;
        q.emplace(u);
      }
    }
    // Build the level graph for all reachable vertices.
    bool succ = false;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : g[u]) {
        if (mb[v] == -1) {
          succ = true;
        } else if (dist[mb[v]] == -1) {
          dist[mb[v]] = dist[u] + 1;
          q.emplace(mb[v]);
        }
      }
    }
    return succ;
  }

  // Find an augmenting path starting at u.
  bool dfs(int u) {
    for (int v : g[u]) {
      if (mb[v] == -1 || (dist[mb[v]] == dist[u] + 1 && dfs(mb[v]))) {
        ma[u] = v;
        mb[v] = u;
        return true;
      }
    }
    dist[u] = -1;  // Mark this point as inreachable after one visit.
    return false;
  }

  // Hopcroft-Karp maximum matching algorithm.
  std::vector<std::pair<int, int>> hopcroft_karp_maximum_matching() {
    // Build the level graph and then find a blocking flow.
    while (bfs()) {
      for (int u = 0; u < n1; ++u) {
        if (ma[u] == -1) {
          dfs(u);
        }
      }
    }
    // Collect the matched pairs.
    std::vector<std::pair<int, int>> matches;
    matches.reserve(n1);
    for (int u = 0; u < n1; ++u) {
      if (ma[u] != -1) {
        matches.emplace_back(u, ma[u]);
      }
    }
    return matches;
  }
};

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
  int n1, n2, m;
  std::cin >> n1 >> n2 >> m;
  BipartiteGraph gr(n1, n2);
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    gr.add_edge(u, v);
  }
  auto res = gr.hopcroft_karp_maximum_matching();
  std::cout << res.size() << '\n';
  for (int i = 0; i < res.size(); ++i) {
    std::cout << res[i].first << ' ' << res[i].second << '\n';
  }
  return 0;
}

Reduction to Maximum Flow

The bipartite maximum matching problem can be reduced to a maximum flow problem.

As shown, add two vertices as source and sink. Connect an edge from the source to each left vertex; connect an edge from each right vertex to the sink; and for each undirected edge in the bipartite graph, connect an edge from the left vertex to the right vertex. All edges have capacity \(1\). Each flow in the resulting directed graph corresponds one-to-one with a matching in the bipartite graph, and the flow value equals the size of the corresponding matching. Therefore, solving the bipartite maximum matching problem is equivalent to solving the maximum flow in the corresponding directed graph.

Any algorithm that can solve the maximum flow problem can be used to solve the bipartite maximum matching problem. It is easy to see that Kuhn's algorithm and the Hopcroft–Karp algorithm are special cases of the corresponding algorithms for maximum flow. Similarly, push-relabel algorithms can also be used to solve bipartite maximum matching. However, it should be noted that any maximum flow algorithm, when applied to bipartite maximum matching, needs to be optimized accordingly to avoid large constant factors.

Linear Programming Formulation

Like other maximum flow problems, the maximum matching problem in a bipartite graph \(G=(V,E)\) can be written as a linear programming problem. If \(x_e\in\{0,1\}\) indicates whether edge \(e\) belongs to the matching, we obtain the following linear program:

\[ \begin{aligned} \max_{\{x_e\}}\;& \sum_{e\in E}x_e \\ \text{subject to } & \sum_{e\sim v} x_{e} \le 1,~\forall v\in V,\\ & x_e\ge 0,~\forall e\in E. \end{aligned} \]

Here, \(e\sim v\) denotes incidence, meaning vertex \(v\) is one endpoint of edge \(e\). Besides non-negativity constraints, the constraints require that each vertex \(v\in V\) is incident to at most one edge, which is exactly the definition of a matching. Thus, all matchings correspond to some integer points in the feasible region of this linear program.

The converse is not true. In a feasible solution, \(x_e\) may be fractional, which does not represent any actual matching. Nevertheless, for bipartite graphs \(G\), all extreme point solutions of this linear program are integer points. This means the optimal value of the objective function can always be achieved at an integer point, without considering non-integer cases. This property does not hold for general graphs, so the above linear program is not equivalent to the maximum matching problem in general graphs.

The dual of this linear program can be written as:

\[ \begin{aligned} \min_{\{y_v\}}\;& \sum_{v\in V}y_v \\ \text{subject to } & y_u+y_v \ge 1,~\forall (u,v)\in E,\\ & y_v\ge 0,~\forall v\in V. \end{aligned} \]

As we will see, this is exactly the minimum vertex cover problem for bipartite graphs.

Dulmage–Mendelsohn Decomposition

Using the maximum matching of a bipartite graph, we can partition the vertices into several disjoint subsets, completely characterizing the distribution and structural features of all maximum matchings of the bipartite graph. This is the Dulmage–Mendelsohn decomposition. In algorithm competitions, this decomposition can be used to identify critical vertices and critical edges in maximum matchings, and to determine the uniqueness of maximum matchings or solve bipartite game problems.

Construction Method

Let \(M\) be a maximum matching of the bipartite graph \(G=(X,Y,E)\).

As shown, we can define the following three subsets for all vertices \(V=X\cup Y\):

Even-reachable vertices \(\mathcal E\): the set of all vertices reachable from an unmatched vertex via an alternating path of even length;
Odd-reachable vertices \(\mathcal O\): the set of all vertices reachable from an unmatched vertex via an alternating path of odd length;
Unreachable vertices \(\mathcal U\): the set of all vertices not reachable from any unmatched vertex via an alternating path.

It can be proven that the three vertex sets \(\mathcal E,\mathcal O,\mathcal U\) obtained in this way have the following properties:

Properties

The sets \(\mathcal E,\mathcal O,\mathcal U\) form a partition of the vertex set, and this partition is independent of the choice of the maximum matching \(M\).
Every maximum matching of \(G\) contains a perfect matching among the vertices of \(\mathcal U\), and matches every vertex in \(\mathcal O\) to a vertex in \(\mathcal E\). That is, the size of a maximum matching of \(G\) equals \(|\mathcal O|+|\mathcal U|/2\).
There are no edges in \(G\) connecting a vertex in \(\mathcal E\) to a vertex in \(\mathcal E\cup\mathcal U\).

Proof

By definition, \(\mathcal U\) and \(\mathcal E\cup\mathcal O\) are disjoint. We only need to prove \(\mathcal E\) and \(\mathcal O\) are disjoint. Suppose not; for a vertex \(v\in\mathcal E\cap\mathcal O\), there exists an alternating path of even length from an unmatched vertex \(a\) to \(v\), and also an alternating path of odd length from an unmatched vertex \(b\) to \(v\). Since \(G\) is bipartite, \(a\neq b\), and the edges arriving at \(v\) in the two paths are matching and non-matching respectively. Therefore, concatenating the two paths gives an alternating path from \(a\) through \(v\) to \(b\). This is an augmenting path, contradicting that \(M\) is a maximum matching. Hence, \(\mathcal E\cap\mathcal O=\varnothing\).

Let \(M'\) be a maximum matching different from \(M\). Repeating the proof of Berge's Lemma shows that \(M'\oplus M\) consists only of even-length paths and even cycles. Starting from the maximum matching \(M\), we can flip the edges (swap matching and non-matching edges) in each connected component (paths and cycles) one by one to obtain the maximum matching \(M'\). Flipping an even cycle leaves unmatched vertices unmatched, and the parity of the length of alternating paths from them does not change; flipping an even-length path swaps the matching status of the two endpoints, but the parity of the path length from them to any vertex on the path remains consistent. Therefore, during the flipping process, the sets \(\mathcal E,\mathcal O,\mathcal U\) remain unchanged. This shows the decomposition is independent of the choice of \(M\).
If a matching edge appears in an alternating path starting from an unmatched vertex \(v\), then its two endpoints have different parity of distance from \(v\), so they belong to \(\mathcal E\) and \(\mathcal O\) respectively; otherwise, both endpoints must be in \(\mathcal U\). This means matching edges in a maximum matching are either \(\mathcal E\mathcal O\) edges or \(\mathcal U\mathcal U\) edges. Conversely, unmatched vertices can be reached via an alternating path of length zero from themselves, so they only appear in \(\mathcal E\), meaning vertices in \(\mathcal O\) and \(\mathcal U\) are matched. Simple counting shows the size of a maximum matching is \(|\mathcal O|+|\mathcal U|/2\).
By definition, any vertex \(a\in\mathcal E\) is reachable from an unmatched vertex \(v\) via an alternating path of even length, meaning vertices in \(\mathcal E\) are either unmatched or the alternating path \(P\) reaching them ends with a matching edge. If there is an edge in \(G\) connecting \(a\) to a vertex \(b\in\mathcal E\cup\mathcal U\), then by the previous discussion, this edge must be a non-matching edge, and we can extend the alternating path \(P\) along it. This implies vertex \(b\) also belongs to \(\mathcal O\), contradicting property 1. Therefore, there are no edges in \(G\) connecting a vertex in \(\mathcal E\) to a vertex in \(\mathcal E\cup\mathcal U\).

The resulting vertex partition \(V=\mathcal E\cup\mathcal O\cup\mathcal U\) is called the Dulmage–Mendelsohn decomposition. After obtaining a maximum matching using the algorithms described earlier, the Dulmage–Mendelsohn decomposition can be computed via BFS in \(O(|V|+|E|)\) time.

Critical Vertices in Maximum Matching

A vertex \(v\) is called a critical vertex for maximum matching in a bipartite graph \(G\) if it is matched in every maximum matching of \(G\). The following result shows: a vertex is critical if and only if in some maximum matching, there is no alternating path of even length from an unmatched vertex to it.

Theorem

Let the Dulmage–Mendelsohn decomposition of bipartite graph \(G=(X,Y,E)\) be \(V=\mathcal E\cup\mathcal O\cup\mathcal U\). Then, a vertex \(v\in V\) is critical if and only if \(v\in\mathcal O\cup \mathcal U\).

Proof

According to the properties of the Dulmage–Mendelsohn decomposition, in any maximum matching of \(G\), vertices in \(\mathcal O\) and \(\mathcal U\) must be matched. Therefore, vertices in \(\mathcal O\cup \mathcal U\) are critical. Next, we need to show that there are no critical vertices in \(\mathcal E\). If in a maximum matching \(M\), a vertex \(a\in\mathcal E\) is critical, then there is an alternating path \(P\) of even length connecting \(a\) to some unmatched vertex \(b\in\mathcal E\). Flipping all edges on this path yields a maximum matching \(M\oplus P\) in which \(a\) becomes unmatched. Hence, there are no critical vertices in \(\mathcal E\).

Therefore, to find critical vertices for maximum matching, it suffices to compute the Dulmage–Mendelsohn decomposition.

Critical Edges in Maximum Matching

Similarly, an edge \(e\) is called a critical edge for maximum matching in a bipartite graph \(G\) if it is a matching edge in every maximum matching of \(G\). The maximum matching of a bipartite graph is unique if and only if all matching edges in one of its maximum matchings are critical edges.

Theorem

Let the Dulmage–Mendelsohn decomposition of bipartite graph \(G=(X,Y,E)\) be \(V=\mathcal E\cup\mathcal O\cup\mathcal U\), and let \(M\) be a maximum matching of \(G\). Then, an edge \(e\in E\) is critical if and only if both endpoints of \(e\) are in \(\mathcal U\), \(e\) is a matching edge in \(M\), and there is no alternating cycle containing \(e\) relative to \(M\).

Proof

The endpoints of a critical edge must be critical vertices. According to the properties of the Dulmage–Mendelsohn decomposition, edges in a maximum matching can only be \(\mathcal E\mathcal O\) edges or \(\mathcal U\mathcal U\) edges. However, there are no critical vertices in \(\mathcal E\), so critical edges can only be \(\mathcal U\mathcal U\) edges. Of course, a critical edge must also be a matching edge in \(M\). Let \(e\in M\) be a \(\mathcal U\mathcal U\) edge. It is not critical if and only if there exists another maximum matching \(M'\neq M\) such that \(e\in M\oplus M'\). Repeating the proof of Berge's Lemma shows that \(M'\oplus M\) consists only of even-length paths and even cycles. One endpoint of these paths is an unmatched vertex relative to \(M\), so vertices on the path are not in \(\mathcal U\), contradicting the choice of \(e\). Therefore, \(e\) can only appear in an even cycle. Thus, a \(\mathcal U\mathcal U\) edge \(e\in M\) is not critical if and only if there exists an alternating cycle containing \(e\) relative to \(M\). This is what we needed to prove.

Therefore, to find critical edges for maximum matching, follow these steps:

Find a maximum matching \(M\) of \(G\);
Orient the edges of \(G\) according to \(M\) to obtain a directed graph \(G_M\);
Perform BFS to find the set \(\mathcal U\) in the Dulmage–Mendelsohn decomposition, i.e., vertices not reachable from any unmatched vertex via an alternating path;
Use Tarjan's algorithm to find all strongly connected components of \(G_M\);
Traverse the edges in matching \(M\); if both endpoints are in \(\mathcal U\) but not in the same strongly connected component, it is a critical edge.

After obtaining the maximum matching, the subsequent steps take \(O(|V|+|E|)\) time.

Using algorithms for bipartite maximum matching, other combinatorial optimization problems can be solved.

Minimum Vertex Cover in Bipartite Graphs

The minimum vertex cover problem is to select the smallest set of vertices in an undirected graph such that every edge has at least one endpoint selected.

The minimum vertex cover problem for general graphs is NP-hard, but for bipartite graphs, Kőnig's theorem shows it can be reduced to the maximum matching problem and solved efficiently. The proof of the theorem also gives a construction for the minimum vertex cover.

Kőnig's Theorem

In a bipartite graph, the number of vertices in a minimum vertex cover equals the number of edges in a maximum matching.

Proof

Let \(M\) be a maximum matching of the bipartite graph \(G=(X,Y,E)\). Let \(Z\) be the set of vertices reachable from an unmatched left vertex \(U\) via some alternating path. Then, the vertex set \(C=(X\setminus Z)\cup(Y\cap Z)\) is the desired minimum vertex cover.

First, \(C\) is a vertex cover. Suppose not; there exists an edge \((u,v)\in E\) such that \(u\in X\cap Z\) and \(v\in Y\setminus Z\). Let \(P_u\) be an alternating path reaching \(u\). If \((u,v)\) is a matching edge, then the last edge in \(P_u\) is \((v,u)\), contradicting \(v\notin Z\); if \((u,v)\) is not a matching edge, then we can extend \(P_u\) along \((u,v)\) to get an alternating path reaching \(v\), again contradicting \(v\notin Z\). These contradictions show every edge has at least one endpoint in \(C\), so \(C\) is a vertex cover.

Next, we need to show \(C\) is minimum. To cover all edges of the maximum matching \(M\), any vertex cover needs at least \(|M|\) vertices. Therefore, we only need to prove \(|C|=|M|\), then it must be minimum. This is equivalent to proving that besides containing exactly one endpoint of each matching edge, \(C\) contains no other vertices; i.e., \(C\) contains no unmatched vertices. Suppose not; there exists an unmatched vertex \(v\in C\). If \(v\in X\), then \(v\in U\subseteq Z\), contradicting the construction of \(C\); if \(v\in Y\), then an alternating path to \(v\) is an augmenting path relative to \(M\), which by Berge's Lemma contradicts \(M\) being maximum. These contradictions show no such unmatched vertex exists, so \(C\) is a minimum vertex cover.

From a network flow perspective, the minimum vertex cover problem is the minimum cut problem: selecting a left vertex corresponds to cutting its edge from the source; selecting a right vertex corresponds to cutting its edge to the sink. From a linear programming perspective, the minimum vertex cover problem is the dual of the maximum matching problem. Therefore, Kőnig's theorem can be seen as a special case of the max-flow min-cut theorem, or more generally, a special case of the strong duality theorem of linear programming.

Maximum Independent Set in Bipartite Graphs

The maximum independent set problem is to select the largest set of vertices in an undirected graph such that no two are adjacent.

For general graphs, the following theorem holds:

Theorem

In a graph \(G=(V,E)\), a vertex set \(C\subseteq V\) is a vertex cover if and only if its complement \(V\setminus C\) is an independent set.

Proof

\(C\) is a vertex cover if and only if for every edge \(e\in E\), at least one endpoint appears in \(C\), if and only if no edge has both endpoints in \(V\setminus C\), if and only if \(V\setminus C\) is an independent set.

Corollary

In a graph \(G=(V,E)\), the sum of the sizes of a minimum vertex cover and a maximum independent set equals the number of vertices.

Therefore, like the minimum vertex cover problem, the maximum independent set problem is NP-hard for general graphs, but for bipartite graphs it can be reduced to the maximum matching problem and solved efficiently.

Minimum Path Cover in Directed Acyclic Graphs

The minimum path cover problem is to select the smallest number of simple paths in a directed graph such that every vertex appears in exactly one path.

The minimum path cover problem for general directed graphs is NP-hard, but for directed acyclic graphs (DAGs), it can be reduced to bipartite maximum matching. For a DAG \(G=(V,E)\), construct a bipartite graph \(G'=(V^\text{in},V^\text{out},E')\) as follows:

For each vertex \(v\in V\), create an in-vertex \(v^\text{in}\) and an out-vertex \(v^\text{out}\). Let the sets of all in-vertices and out-vertices be \(V^\text{in}\) and \(V^\text{out}\), respectively. They become the left and right parts of the new graph.
For each directed edge \((u,v)\in E\), create an undirected edge \((u^\text{out},v^\text{in})\). The set of all such undirected edges is \(E'\).

For this, we have the following result:

Theorem

For a directed acyclic graph \(G=(V,E)\), the size of a minimum path cover plus the size of a maximum matching in the corresponding bipartite graph \(G'=(V^\text{in},V^\text{out},E')\) equals the number of vertices.

Proof

Each matching \(M'\) in \(G'\) corresponds to a subgraph \(F\) of \(G\), where each vertex in \(F\) has in-degree and out-degree at most one, meaning \(F\) is actually a collection of vertex-disjoint paths or cycles in \(G\). However, we assume \(G\) has no cycles, so \(F\) consists only of disjoint paths. Conversely, for each such subgraph \(F\), we can construct a corresponding matching. Since the size of the matching \(M\) equals the number of vertices minus the number of paths in \(F\), the minimum path cover problem in \(G\) corresponds to the maximum matching problem in \(G'\).

The proof is constructive, so it is easy to construct the corresponding minimum path cover from the obtained maximum matching. Moreover, this construction shows that for general directed graphs, this reduction no longer holds precisely because matchings in the bipartite graph may correspond to cycles in the directed graph.

In particular, for a set \(X\) with a partial order \(P\), we can construct a DAG \(G=(X,P)\). Then, by Dilworth's theorem, the size of a minimum path cover in \(G\) equals the length of its longest antichain, i.e., the width of the poset \((X,P)\). Therefore, this section actually provides an efficient method to compute the width of any poset.

Examples

The difficulty in applying bipartite matching lies in graph construction. This section demonstrates construction techniques through some examples.

Luogu P1129 Matrix Game

There is a 01 matrix. You can swap any two rows or two columns. Determine if it is possible to swap so that all entries on the main diagonal (top-left to bottom-right) are 1.

Solution

Note that if there exist \(n\) ones such that no two are in the same row or column, then a solution exists; otherwise, no solution exists. The problem reduces to whether we can find these \(n\) ones.

Consider a 1: selecting it in the final solution means its row and column are occupied. Thus, we can build a bipartite graph with \(n\) left vertices and \(n\) right vertices, where for each 1 at position \((i,j)\), we add an edge connecting left vertex \(i\) (row) and right vertex \(j\) (column). Then we can perform bipartite matching.

Code

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int ct, n, t[100010], x, r[100010], ans, vis[100010], dis[100010];
vector<int> to[100010];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + n + 1, 0);
  fill(dis + 1, dis + n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  for (cin >> ct; ct--;) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        cin >> x;
        if (x) {
          to[i].push_back(j);
        }
      }
    }
    for (; BFS();) {
      for (int i = 1; i <= n; i++) {
        if (!t[i] && DFS(i)) {
          ans++;
        }
      }
    }
    cout << (ans == n ? "Yes" : "No") << '\n';
    for (int i = 1; i <= n; i++) {
      t[i] = r[i] = 0;
      to[i].clear();
    }
    ans = 0;
  }
  return 0;
}

Gym 104427B Lawyers

There are \(n\) lawyers, each accused of fraud. They need to defend each other to ensure every lawyer is acquitted. These \(n\) lawyers have \(m\) trust relationships; a trust relationship \((a, b)\) means \(a\) can defend \(b\). Any lawyer who is defended will be acquitted, except one case: if \(a\) and \(b\) defend each other, both will be found guilty.

Determine if it is possible to acquit every lawyer.

Solution

For each unordered pair \((a, b)\), if \(a\) can defend \(b\), add an edge from this unordered pair to \(b\), and vice versa.

Keep only \((a, b)\) that have edges; the problem is transformed into a bipartite maximum matching with \(m\) left vertices and \(n\) right vertices.

Code

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int n, k, u, v, t[200020], r[200020], ans, vis[200020], dis[200020], c;
map<pair<int, int>, int> mp;
vector<int> to[200020];
queue<int> q;

int DFS(int x) {
  if (vis[x]) {
    return 0;
  }
  vis[x] = 1;
  for (auto i : to[x]) {
    if (!r[i]) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
    if (dis[r[i]] == dis[x] + 1 && DFS(r[i])) {
      r[i] = x;
      t[x] = i;
      return 1;
    }
  }
  return 0;
}

int BFS() {
  fill(vis + 1, vis + n + 1, 0);
  fill(dis + 1, dis + n + 1, 0);
  for (int i = 1; i <= n; i++) {
    if (!t[i]) {
      q.push(i);
      dis[i] = 1;
    }
  }
  int f = 0;
  for (; q.size(); q.pop()) {
    int tmp = q.front();
    for (auto i : to[tmp]) {
      if (!r[i]) {
        f = 1;
      }
      if (r[i]) {
        if (!dis[r[i]]) {
          dis[r[i]] = dis[tmp] + 1;
          q.push(r[i]);
        }
      }
    }
  }
  return f;
}

void mxf() {
  for (; BFS();) {
    for (int i = 1; i <= n; i++) {
      if (!t[i] && DFS(i)) {
        ans++;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> u >> v;
    if (mp.find({u, v}) == mp.end()) {
      mp[{u, v}] = mp[{v, u}] = ++c;
    }
    to[v].push_back({mp[{u, v}]});
  }
  mxf();
  cout << (ans == n ? "YES" : "NO") << '\n';
  ans = 0;
  return 0;
}

Codeforces 1404E Bricks

Cover an \(n \times m\) grid exactly with some \(1 \times x\) bricks (bricks can be rotated), where some cells cannot be covered.

???

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

Maximum Bipartite Matching

Introduction

Kuhn's Algorithm

Process

Optimizations

Reference Implementation

Hopcroft–Karp Algorithm

Process

Optimization

Reference Implementation

Reduction to Maximum Flow

Linear Programming Formulation

Dulmage–Mendelsohn Decomposition

Construction Method

Critical Vertices in Maximum Matching

Critical Edges in Maximum Matching

Related Problems

Minimum Vertex Cover in Bipartite Graphs

Maximum Independent Set in Bipartite Graphs

Minimum Path Cover in Directed Acyclic Graphs

Examples