What is Blossom Algorithm - Explained

Blossom Algorithm

Today we are going to discuss what is blossom algorithm. Actually is an algorithm in graph theory for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph G = (V, E), the algorithm finds a matching M such that vertex in V is incident with at one edge in M ​​and | M | is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.

Edmond's Blossom Algorithm

A major reason that the algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. Another reason is that it led to a linear polyhedral description of the matching polytope, yielding an algorithm for min-weight matching.As elaborated by Alexander Schrijver, further significance of the result comes from the fact that this was the first polytope whose proof of integrality "does not simply follow from total unimodularity, and its description was a breakthrough in polyhedral combinatorics." 

Blossom algorithm

It is all in one: an amazing algorithm, an amazing presentation of the result, simple enough to be understood but yet complex, a beginning of a whole new field, one of the main reasons why we measure complexity of an algorithm the way we do - to name a few.

The algorithm appeared in the paper named: “Paths, Trees and Flowers” and it was something. It was the first polynomial algorithm for the maximum matching problem. It was a polynomial algorithm when we were still not sure what is the right measure for the speed of an algorithm.

Years are 60’s. Computer are “weak”. Practically, at this stage, we don’t even care for asymptotic difference in (sub)exponential and quadratic/cubic running time - they are the same for the sizes that these computers could handle. But, scientist knew we will need it sooner rather than later. Edmonds argued why do we even need such a measure and asked for a formalisation - as this is not already enough. But the magic is just about to start. Let me present just some ideas and hopefully motivate you to look it up.

The maximum matching problems is: Given a graph G$G$ find the maximum number of edges such that no two have a common endpoint.

The sets of red edges are the maximum matchings in corresponding graphs.

How do we find such a matching? The starting point is the following theorem: A matching M$M$ is of the maximum size if and only if there is no augmenting path for M$M$.

So, what do you do: start with any matching. Check if there is augmenting path for M$M$. If there is one then augment and you have a bigger matching. Otherwise you already have the maximum matching. See the above figure.

Therefore, the goal is to check if there is an augmenting path. How to find it. We start from one exposed vertex (not still covered by M$M$) and try to build an augmenting paths. If we do great, but we usually don’t make it. What Edmonds showed is that if we don’t build it then either

• it does not exist (again good)
• we made an odd cycle and we don’t know how to proceed.

We call such an odd cycle - blossom. The part of the path that is not in the blossom is called, appropriately, a stem. To proceed now, Edmonds shows that we can simply contract the blossom and proceed on the contracted graph as shown below:

The key is, if we find an augmenting path in the contracted instance we can return it back and we will have an augmenting path in the original graph (see figure below), and if there isn’t one in the contracted instance then there is no augmenting path in the starting graph.

Now? Repeat. Done.

More magic? Go to the maximum weighted matching - Edmonds gave a linear program formulation for which the vertices of the matching polytope are integer, so you can use linear programming to find it or even better to use primal dual as Edmonds showed.