Bipartite Matching: Algorithms and Applications

1. Bipartite Graphs and Matchings

Let's begin by formalizing the problem. Imagine you have a set of applicants and a set of open positions. An edge exists between an applicant and a position if the applicant is qualified for it. The goal is to hire as many people as possible, with the constraint that each applicant can take at most one job, and each job can be filled by at most one applicant. This is a classic bipartite matching problem.

A bipartite graph is a graph $G=(V,E)$ whose vertices $V$ can be divided into two disjoint and independent sets, $U$ and $V$, such that every edge in $E$ connects a vertex in $U$ to one in $V$. There are no edges within $U$ or within $V$.

A matching $M$ in a graph is a subset of its edges such that no two edges in $M$ share a common vertex.

A maximum matching (or maximum cardinality matching) is a matching that contains the largest possible number of edges.

The following video provides an excellent visual introduction to these concepts using the job assignment analogy.

A simple way to check if a graph is bipartite is to try and color it with two colors. Starting from an arbitrary vertex, color it red. Then, color all its neighbors blue. Then, color all their uncolored neighbors red, and so on. If you ever find an edge connecting two vertices of the same color, the graph is not bipartite. This can be implemented efficiently using Breadth-First Search (BFS).

2. The Augmenting Path Method

A greedy approach, like the one tried in the "books and people" example in one of our upcoming resources, often fails to find a maximum matching. We need a more systematic way to improve an existing matching. The key to this is the concept of an augmenting path.

An augmenting path with respect to a matching $M$ is a simple path in the graph that:

1. Starts at an unmatched vertex in one partition (say, $U$).
2. Ends at an unmatched vertex in the other partition ($V$).
3. Alternates between edges that are not in $M$ and edges that are in $M$.

If we find such a path, we can increase the size of our matching by one. We do this by "flipping" the edges along the path: we remove the path's matched edges from $M$ and add the path's unmatched edges to $M$. Since the path starts and ends with an unmatched edge, it contains one more unmatched edge than matched edges. This flip, therefore, results in a new matching with exactly one more edge.

This leads to a profound result known as Berge's Theorem:

A matching $M$ in a graph $G$ is a maximum matching if and only if there are no augmenting paths with respect to $M$.

This theorem gives us a complete algorithm: start with any matching (even an empty one) and repeatedly find and "flip" augmenting paths until no more can be found.

The next video segment beautifully illustrates this idea of "clever swaps."

3. Finding Augmenting Paths

Berge's theorem tells us what to look for, but how do we find an augmenting path efficiently? We can use a graph traversal algorithm like BFS or DFS.

Here is the general procedure using BFS, starting from the set of vertices $U$:

1. Initialize an empty matching $M$.
2. For every unmatched vertex $u\in U$:
   a. Run a BFS or DFS starting from $u$ to find an alternating path to any unmatched vertex $v\in V$.
   b. The traversal must be modified: from a vertex in $U$, you can only traverse an edge not in $M$. From a vertex in $V$, you can only traverse an edge that is in $M$.
   c. If such a path is found, augment the matching $M$ by flipping the edges along the path. Break the inner loop and start again from the new, larger matching.
3. If the loop completes without finding any augmenting paths for any of the unmatched vertices in $U$, the current matching $M$ is maximum.

The complexity of finding one augmenting path using BFS/DFS is $O(E)$, where $E$ is the number of edges. Since in the worst case we might find a path for up to $|V|/2$ vertices, the total complexity of this naive Ford-Fulkerson-style method for matching is $O(V\cdot E)$.

The following video demonstrates this search process.

4. Hopcroft-Karp and the Max-Flow Method

While the $O(V\cdot E)$ algorithm is correct, more efficient methods exist. For your GATE exam, you should be aware of these.

Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm improves upon the simple augmenting path search. Instead of finding one path at a time, it performs the following in each phase:

1. Use BFS to find all the shortest augmenting paths.
2. Use DFS to find a maximal set of vertex-disjoint paths among these shortest paths.
3. Augment the matching with all paths in this set simultaneously.

By augmenting with multiple paths in one phase, it reaches the maximum matching much faster. Its time complexity is $O(E\sqrt{V})$, which is a significant improvement and the most efficient known algorithm for unweighted bipartite matching. For GATE, you are not expected to implement this but should know its name and complexity.

Reduction to Maximum Flow

An entirely different and very powerful way to solve bipartite matching is to transform it into a maximum flow problem. Given your IT background, you've likely encountered max-flow algorithms (like Edmonds-Karp or Dinic). The conversion is elegant:

1. Given a bipartite graph $G=(U\cup V,E)$, create a new directed graph (a flow network).
2. Add a source node $s$ and a sink node $t$.
3. For every vertex $u\in U$, add a directed edge from $s$ to $u$ with a capacity of 1.
4. For every vertex $v\in V$, add a directed edge from $v$ to $t$ with a capacity of 1.
5. For every original edge $(u,v)$ in $G$ (with $u\in U,v\in V$), add a directed edge from $u$ to $v$ with a capacity of 1 (or infinity, as the flow is limited by the source/sink edges).

Now, run any max-flow algorithm on this network. The Max-Flow Min-Cut Theorem implies that the value of the maximum flow from $s$ to $t$ is exactly equal to the size of the maximum matching in the original bipartite graph. The edges from $U$ to $V$ that have a flow of 1 in the solution correspond to the edges in the maximum matching.

This reduction is a critical technique to have in your toolkit for GATE, as it connects two major topics in algorithms.

Conclusion

In this lesson, we tackled the problem of finding the maximum number of independent pairs in a bipartite graph. We saw that a simple greedy approach can fail, leading us to the powerful concept of the augmenting path.

Key Takeaways:

• A bipartite graph models relationships between two distinct groups of items.
• A matching is a set of edges with no shared vertices; a maximum matching has the largest possible size.
• An augmenting path is an alternating path between two unmatched vertices. According to Berge's Theorem, a matching is maximum if and only if no such path exists.
• We can find a maximum matching by repeatedly finding and "flipping" augmenting paths. A simple implementation using BFS/DFS has a complexity of $O(V\cdot E)$.
• The Hopcroft-Karp algorithm is a more efficient method that finds multiple shortest augmenting paths in each phase, running in $O(E\sqrt{V})$ time.
• Bipartite matching can be solved by converting the graph into a flow network and finding the maximum flow. The max flow value equals the size of the maximum matching.

In our next lesson, we will shift gears to another fundamental graph problem: Graph Coloring. Instead of selecting edges, we will focus on assigning "colors" (labels) to vertices under certain constraints, a problem with applications in scheduling, register allocation, and many other areas of computer science.