Maximum matching in a general graph.

Edges contained in the matching are colored blue.

An often occuring and well-studied problem in graph theory is finding a maximum matching in a graph \( G=(V,E)\). A matching M is a subset of edges such that every node is covered by at most one edge of the matching. M is a maximum matching if there is no other matching in G that has more edges than M.

This website is about Edmonds's Blossom Algorithm, an algorithm that computes a maximum matching in an undirected graph. In contrast to some other matching algorithms, the graph need not be bipartite. The algorithm was introduced by Jack Edmonds in 1965 and has been further improved since then. Many exact modern algorithms for the maximum matching problem on general graphs are still based on the ideas of the Blossom Algorithm.

Edmonds's Blossom Algorithm uses and extends the essential ideas of the Hopcroft-Karp algorithm, which computes a maximum matching for bipartite graphs. If you have not heard about this algorithm, we recommend having a look at it before proceeding with the Blossom Algorithm: Hopcroft-Karp Algorithm

We further assume that you are familiar with graph traversal, especially Breadth-First Search.

- To create a node, make a double-click in the drawing area.
- To create an edge, first click on the output node and then click on the destination node.
- Right-clicking deletes edges and nodes.

A
occured when reading from file:
the contents:

yellow: free node | |

red stroke: root of the BFS | |

red: currently active node in BFS | |

orange: currently checked neighbor in BFS | |

green: node on the augmenting path | |

large radius: contracted node | |

orange: currently checked edge in BFS | |

blue: matched edge | |

grey overlay: edge in BFS tree | |

green overlay: edge on the augmenting path |

The algorithm is ready to start now. Click "next" to execute a single step of the algorithm, "prev" to go one step back and "fast forward" for a fast execution of the algorithm.

The BFS queue is empty. No augmenting path has been found by the modified Breadth-First Search.

The augmenting path is inverted to improve the matching. Inverting an augmenting path means that all unmatched edges along the path are changed to matched ones and vice versa. By doing so, the number of edges contained in the matching increases by 1. The new matching is colored blue.

There are still unmatched vertices (yellow). We call them free vertices. We try to find an augmenting path to improve the matching. An augmenting path starts and ends at a free vertex and alternates between unmatched and matched edges.

We pick one of the free vertices as the root node of a modified Breadth-First Search (BFS). Its stroke is colored red throughout the execution of the BFS. From the root node, we will construct a tree of alternating paths (BFS tree) until we reach another free vertex.

There are no neighbors left that we could check from the currently active node so we continue the BFS with the next node.

The odd-length cycle we found is contracted to a single supernode. Supernodes are highlighted by a larger radius compared to the other nodes. We further push the new supernode to the BFS queue.

Pick the next node from the BFS queue. We call this node the currently active node and color it red. From this node, we will explore its neighbors to look for a free vertex.

We add the neighbor and its mate to the BFS tree. The mate is further pushed to the BFS queue and we might continue our search from there later. The edges of the BFS tree are highlighted by a grey overlay.

We can ignore even-length cycles. There is nothing to do in this case.

We check the next neighbor (orange) and find that it is already matched.

We check the next neighbor (orange edge) and find that it is a free vertex (yellow). Thus, there is an augmenting path between the root of the BFS and this vertex.

We check the next neighbor (orange) and find that this node is already contained in the BFS tree. Thus, there exists a cycle and we see that it has an odd number of edges. We call such a cycle a blossom.

We check the next neighbor (orange) and find that this node is already contained in the BFS tree. Thus, there exists a cycle and we see that it has an even number of edges.

The augmenting path is highlighted green. Before improving the matching we have to expand the supernodes contained in the graph.

One of the supernodes is expanded and the augmenting path is adjusted correctly. There are still supernodes left that have to be expanded.

The augmenting path from the BFS root to the free vertex found has been fully reconstructed and is highlighted green.

After the expansion of all supernodes the augmenting path is fully reconstructed and highlighted green.

There are no free vertices in the graph anymore so we have found a matching of maximum cardinality. Its edges are colored blue.

BEGIN

WHILE F != ∅ DO (*set of free nodes F*)

pick r ∈ F

queue.push(r) (*BFS queue*)

T ← ∅ (*BFS tree T*)

T.add(r)

WHILE queue != ∅

v ← queue.pop()

FOR ALL neighbors w of v DO

IF w ∉ T AND w matched THEN

T.add(w)

T.add(mate(w))

queue.push(mate(w))

ELSE IF w ∈ T AND even-length

cycle detected THEN

CONTINUE

ELSE IF w ∈ T AND odd-length

cycle detected THEN

contract cycle

ELSE IF w ∈ F THEN

expand all contracted nodes

reconstruct augmenting path

invert augmenting path

END

You can open another browser window to read the description in parallel.