A **Matching** in a graph **G = (V, E)** is a subset **M** of **E** edges in **G** such that no two of which meet at a common vertex.

**Maximum Cardinality Matching (MCM)** problem is a Graph Matching problem where we seek a matching **M** that contains the largest possible number of edges. A possible variant is **Perfect Matching** where all **V** vertices are matched, i.e., the cardinality of **M** is **V/2**.

A **Bipartite Graph** is a graph whose vertices can be partitioned into two disjoint sets **U** and **V** such that every edge can only connect a vertex in **U** to a vertex in **V**.

**Maximum Cardinality Bipartite Matching (MCBM)** problem is the **MCM** problem in a Bipartite Graph, which is a lot easier than **MCM** problem in a General Graph.

This visualization is currently limited to unweighted graphs only. Thus, we currently do not support Graph Matching problem variants involving weighted graphs...

To switch between the unweighted **MCBM** (default, as it is much more popular) and unweighted **MCM** mode, click the respective header.

Here is an example of **MCM** mode. In **MCM** mode, one can draw a **General**, not necessarily **Bipartite** graphs. However, the graphs are unweighted (all edges have uniform weight 1).

The available algorithms are different in the two modes.

You can view the visualisation here!

For **Bipartite Graph** visualization, we will re-layout the vertices of the graph so that the two disjoint sets (**U** and **V**) are clearly visible as Left (**U**) and Right (**V**) sets. For **General Graph**, we do not relayout the vertices.

Initially, edges have grey color. Matched edges will have black color. Free/Matched edges along an augmenting path will have Orange/Light Blue colors, respectively.

There are three different sources for specifying an input graph:

**Draw Graph**: You can draw**any**undirected unweighted graph as the input graph (note that in**MCBM**mode, the drawn input graph will be relayout into a nice**Bipartite**graph layout during algorithm animation),**Modeling**: A lot of graph problems can be reduced into an**MCBM**problem. In this visualization, we have the modeling examples for the famous Rook Attack problem (currently disabled) and standard**MCBM**problem (also valid in**MCM**mode).**Examples**: You can select from the list of our example graphs to get you started. The list of examples are slightly different in the two**MCBM**vs**MCM**modes.

There are several Max Cardinality Bipartite Matching (MCBM) algorithms in this visualization, plus one more in Max Flow visualization:

- O(
**VE**)**Augmenting Path Algorithm**(without greedy pre-processing), - O(
**√(V)E**)**Dinic's Max Flow Algorithm**, see__Max Flow__visualization, select Modeling → Bipartite Matching → All 1, then use Dinic's algorithm. - O(
**√(V)E**)**Hopcroft-Karp Algorithm**, - O(
**kE**)**Augmenting Path Algorithm++**(with randomized greedy pre-processing),

PS: Although possible, we will likely not use O(**V ^{3}**)

**Augmenting Path** is a path that starts from a free (unmatched) vertex **u** in graph **G** (note that **G** does not necessarily has to be a bipartite graph), alternates through unmatched, match, ..., unmatched edges in **G**, until it ends at another free vertex **v**. If we flip the edge status along that augmenting path, we will increase the number of edges in the matching set **M** by 1 and eliminates this augmenting path.

In 1957, Claude Berge proposes the following __lemma__: *A matching M in graph G is maximum iff there is no more augmenting path in G*.

The **Augmenting Path Algorithm** is a simple O(**V*(V+E)**) = O(**V ^{2} + VE**) = O(

vi match, vis; // global variables

int Aug(int L) { // return 1 if ∃ an augmenting path from L

if (vis[L]) return 0; // return 0 otherwise

vis[L] = 1;

for (auto& v : AL[L]) {

int R = v.first;

if ((match[R] == -1) || Aug(match[R])) {

match[R] = L;

return 1; // found 1 matching

}

}

return 0; // no matching

}

// in int main(), build the bipartite graph

// use directed edges from left set (of size VLeft) to right set

int MCBM = 0;

match.assign(V, -1);

for (int L = 0; L < VLeft; ++L) {

vis.assign(VLeft, 0);

MCBM += Aug(L); // find augmenting path starting from L

}

printf("Found %d matchings\n", MCBM);

Please see the full implementation at Competitive Programming book repository: __mcbm.cpp__|__py__|__java__|__ml__.

The **MCBM** problem can be modeled as a Max Flow problem. Go to __Max Flow__ visualization page and see the flow graph modeling of MCBM problem (select Modeling → Bipartite Matching → all 1).

If we use one of the fastest Max Flow algorithm, i.e., Dinic's algorithm on this flow graph, we can find Max Flow = MCBM in O(**√(V)E**) time — __analysis omitted for now__. This allows us to solve MCBM problem with **V** ∈ [1000..1500] in a typical 1s allowed runtime in many programming competitions.

If we are given a **Complete** Bipartite Graph **K _{N/2,N/2}**, i.e.,

the Augmenting Path Algorithm discussed earlier will run in O(

This is only OK for **V** ∈ [400..500] in a typical 1s allowed runtime in many programming competitions.

Try executing the **standard** Augmenting Path Algorithm on this , which is an almost complete **K _{5,5}** Bipartite Graph.

The key idea of Hopcroft-Karp (HK) Algorithm (invented in 1973) is identical to __Dinic's Max Flow Algorithm__ discussed earlier, i.e., prioritize shortest augmenting paths (in terms of number of edges used) first. That's it, augmenting paths with 1 edge are processed first before longer augmenting paths with 3 edges, 5 edges, 7 edges, etc (the length always increase by 2 due to the nature of augmenting path in a Bipartite Graph).

Hopcroft-Karp Algorithm has time complexity of O(**√(V)E**) — __analysis omitted for now__. This allows us to solve MCBM problem with **V** ∈ [1000..1500] in a typical 1s allowed runtime in many programming competitions — the similar range as with running Dinic's algorithm on Bipartite Matching flow graph.

Try HK Algorithm on the same **VE**) Augmenting Path Algorithm.

However, we can actually make the easy-to-code **Augmenting Path Algorithm** __discussed earlier__ to avoid its worst case O(**VE**) behavior by doing O(**V+E**) randomized (to avoid adversary test case) greedy pre-processing *before* running the actual algorithm.

This O(**V+E**) additional pre-processing step is simple: For every vertex on the left set, match it with a randomly chosen unmatched neighbouring vertex on the right set. This way, we eliminates many trivial (one-edge) Augmenting Paths that consist of a free vertex **u**, an unmatched edge **(u, v)**, and a free vertex **v**.

Try Augmenting Path Algorithm++ on the same

earlier. Notice that the pre-processing step already eliminates many trivial 1-edge augmenting paths, making the actual Augmenting Path Algorithm only need to do little amount of additional work.Quite often, on **randomly generated** Bipartite Graph, the randomized greedy pre-processing step has cleared most of the matchings.

However, we can construct test case like: **Examples: Randomized Greedy Processing Killer** to make randomization as ineffective as possible. For every group of 4 vertices, there are 2 matchings. Random greedy processing has 50% chance of making mistake per group. Try this case to see for yourself.

The worst case time complexity is no longer O(**VE**) but now O(**kE**) where **k** is a small integer, much smaller than **V**, **k** can be as small as 0 and is at most **V/2**. In our *empirical experiments*, we estimate **k** to be "about √(**V**)" too. This version of Augmenting Path Algorithm++ also allows us to solve MCBM problem with **V** ∈ [1000..1500] in a typical 1s allowed runtime in many programming competitions.

There are two Max Cardinality Matching (MCM) algorithms in this visualization:

- O(
**V^3**)**Edmonds's Matching**algorithm (without greedy pre-processing), - O(
**V^3**)**Edmonds's Matching**algorithm (with greedy pre-processing),

In General Graph, we may have Odd-Length cycle. Augmenting Path is not well defined in such graph, hence we cannot directly implement Claude Berge's lemma like what we did with Bipartite Graph.

Jack Edmonds call a path that starts from a free vertex **u**, alternates between free, matched, ..., free edges, and returns to the **same** free vertex **u** as **Blossom**. This situation is only possible if we have Odd-Length cycle, i.e., non-Bipartite Graph. Edmonds then proposed __Blossom shrinking/contraction and expansion algorithm__ to solve this issue, details verbally.

This algorithm can be implemented in O(**V^3**).

As with the **Augmenting Path Algorithm++** for the MCBM problem, we can also do randomized greedy pre-processing step to eliminate as many 'trivial matchings' as possible upfront. This reduces the amount of work of **Edmonds' Matching Algorithm**, thus resulting in a faster time complexity — analysis TBA.

We have not added visualizations for weighted variant of **MCBM** and **MCM** problems (future work).

You are allowed to use/modify our implementation code for Augmenting Path Algorithm++:__mcbm.cpp____mcbm.java____mcbm.py____mcbm.ml__