Blossom algorithm

Last updated October 13, 2024

In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961,^[1] and published in 1965.^[2] Given a general graph $G = (V, E)$ , the algorithm finds a matching $M$ such that each vertex in $V$ is incident with at most 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.

A major reason that the blossom 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 programming polyhedral description of the matching polytope, yielding an algorithm for min-weight matching.^[4] 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 just from total unimodularity, and its description was a breakthrough in polyhedral combinatorics."^[5]

Augmenting paths

Given $G = (V, E)$ and a matching $M$ of $G$ , a vertex $v$ is exposed if no edge of $M$ is incident with $v$ . A path in $G$ is an alternating path, if its edges are alternately not in $M$ and in $M$ (or in $M$ and not in $M$ ). An augmenting path $P$ is an alternating path that starts and ends at two distinct exposed vertices. Note that the number of unmatched edges in an augmenting path is greater by one than the number of matched edges, and hence the total number of edges in an augmenting path is odd. A matching augmentation along an augmenting path $P$ is the operation of replacing $M$ with a new matching

M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)

.

By Berge's lemma, matching $M$ is maximum if and only if there is no $M$ -augmenting path in $G$ .^[6]^[7] Hence, either a matching is maximum, or it can be augmented. Thus, starting from an initial matching, we can compute a maximum matching by augmenting the current matching with augmenting paths as long as we can find them, and return whenever no augmenting paths are left. We can formalize the algorithm as follows:

   INPUT:  Graph G, initial matching M on G    OUTPUT: maximum matching M* on G A1 functionfind_maximum_matching(G, M) : M* A2     P ← find_augmenting_path(G, M) A3     ifP is non-empty then A4         returnfind_maximum_matching(G, augment M along P) A5     else A6         return M A7     end if A8 end function

We still have to describe how augmenting paths can be found efficiently. The subroutine to find them uses blossoms and contractions.

Blossoms and contractions

Given $G = (V, E)$ and a matching $M$ of $G$ , a blossom $B$ is a cycle in $G$ consisting of $2 k + 1$ edges of which exactly $k$ belong to $M$ , and where one of the vertices $v$ of the cycle (the base) is such that there exists an alternating path of even length (the stem) from $v$ to an exposed vertex $w$ .

Finding Blossoms:

Traverse the graph starting from an exposed vertex.
Starting from that vertex, label it as an outer vertex $o$ .
Alternate the labeling between vertices being inner $i$ and outer $o$ such that no two adjacent vertices have the same label.
If we end up with two adjacent vertices labeled as outer $o$ then we have an odd-length cycle and hence a blossom.

Define the contracted graph $G'$ as the graph obtained from $G$ by contracting every edge of $B$ , and define the contracted matching $M'$ as the matching of $G'$ corresponding to $M$ .

$G'$ has an $M'$ -augmenting path if and only if $G$ has an $M$ -augmenting path, and that any $M'$ -augmenting path $P'$ in $G'$ can be lifted to an $M$ -augmenting path in $G$ by undoing the contraction by $B$ so that the segment of $P'$ (if any) traversing through $v B$ is replaced by an appropriate segment traversing through $B$ .^[8] In more detail:

if $P'$ traverses through a segment $u \to v B \to w$ in $G'$ , then this segment is replaced with the segment $u \to (u' \to \dots \to w') \to w$ in $G$ , where blossom vertices $u'$ and $w'$ and the side of $B$ , $(u' \to \dots \to w')$ , going from $u'$ to $w'$ are chosen to ensure that the new path is still alternating ( $u'$ is exposed with respect to $M\cap B$ , $\{w',w\}\in E\setminus M$ ).

if $P'$ has an endpoint $v B$ , then the path segment $u \to v B$ in $G'$ is replaced with the segment $u \to (u' \to \dots \to v')$ in $G$ , where blossom vertices $u'$ and $v'$ and the side of $B$ , $(u' \to \dots \to v')$ , going from $u'$ to $v'$ are chosen to ensure that the path is alternating ( $v'$ is exposed, $\{u',u\}\in E\setminus M$ ).

Thus blossoms can be contracted and search performed in the contracted graphs. This reduction is at the heart of Edmonds' algorithm.

Finding an augmenting path

The search for an augmenting path uses an auxiliary data structure consisting of a forest $F$ whose individual trees correspond to specific portions of the graph $G$ . In fact, the forest $F$ is the same that would be used to find maximum matchings in bipartite graphs (without need for shrinking blossoms). In each iteration the algorithm either (1) finds an augmenting path, (2) finds a blossom and recurses onto the corresponding contracted graph, or (3) concludes there are no augmenting paths. The auxiliary structure is built by an incremental procedure discussed next.^[8]

The construction procedure considers vertices $v$ and edges $e$ in $G$ and incrementally updates $F$ as appropriate. If $v$ is in a tree $T$ of the forest, we let root(v) denote the root of $T$ . If both $u$ and $v$ are in the same tree $T$ in $F$ , we let distance(u,v) denote the length of the unique path from $u$ to $v$ in $T$ .

    INPUT:  Graph G, matching M on G     OUTPUT: augmenting path P in G or empty path if none found B01 functionfind_augmenting_path(G, M) : P B02    F ← empty forest B03    unmark all vertices and edges in G, mark all edges of M B05    for each exposed vertex vdo B06        create a singleton tree { v } and add the tree to F B07    end for B08    while there is an unmarked vertex v in F with distance(v, root(v)) even do B09        while there exists an unmarked edge e = { v, w } do B10            ifw is not in Fthen                    // w is matched, so add e and w's matched edge to F B11                x ← vertex matched to w in M B12                add edges { v, w } and { w, x } to the tree of v B13            else B14                ifdistance(w, root(w)) is odd then                        // Do nothing. B15                else B16                    ifroot(v) ≠ root(w)then                            // Report an augmenting path in F  $\cup$  { e }. B17                        P ← path (root(v) → ... → v) → (w → ... → root(w)) B18                        returnP B19                    else                            // Contract a blossom in G and look for the path in the contracted graph. B20                        B ← blossom formed by e and edges on the path v → w in T B21                        G’, M’ ← contract G and M by B B22                        P’ ← find_augmenting_path(G’, M’) B23                        P ← lift P’ to G B24                        returnP B25                    end if B26                end if B27            end if B28            mark edge e B29        end while B30        mark vertex v B31    end while B32    return empty path B33 end function

Examples

The following four figures illustrate the execution of the algorithm. Dashed lines indicate edges that are currently not present in the forest. First, the algorithm processes an out-of-forest edge that causes the expansion of the current forest (lines B10 – B12).

Next, it detects a blossom and contracts the graph (lines B20 – B21).

Finally, it locates an augmenting path $P'$ in the contracted graph (line B22) and lifts it to the original graph (line B23). Note that the ability of the algorithm to contract blossoms is crucial here; the algorithm cannot find $P$ in the original graph directly because only out-of-forest edges between vertices at even distances from the roots are considered on line B17 of the algorithm.

Analysis

The forest $F$ constructed by the find_augmenting_path() function is an alternating forest.^[9]

a tree T in G is an alternating tree with respect to M, if
- $T$ contains exactly one exposed vertex $r$ called the tree root
- every vertex at an odd distance from the root has exactly two incident edges in $T$ , and
- all paths from $r$ to leaves in $T$ have even lengths, their odd edges are not in $M$ and their even edges are in $M$ .
a forest F in G is an alternating forest with respect to M, if
- its connected components are alternating trees, and
- every exposed vertex in $G$ is a root of an alternating tree in $F$ .

Each iteration of the loop starting at line B09 either adds to a tree $T$ in $F$ (line B10) or finds an augmenting path (line B17) or finds a blossom (line B20). It is easy to see that the running time is $O(|E||V|^{2})$ .

Bipartite matching

When $G$ is bipartite, there are no odd cycles in $G$ . In that case, blossoms will never be found and one can simply remove lines B20 – B24 of the algorithm. The algorithm thus reduces to the standard algorithm to construct maximum cardinality matchings in bipartite graphs^[7] where we repeatedly search for an augmenting path by a simple graph traversal: this is for instance the case of the Ford–Fulkerson algorithm.

Weighted matching

The matching problem can be generalized by assigning weights to edges in $G$ and asking for a set $M$ that produces a matching of maximum (minimum) total weight: this is the maximum weight matching problem. This problem can be solved by a combinatorial algorithm that uses the unweighted Edmonds's algorithm as a subroutine.^[6] Kolmogorov provides an efficient C++ implementation of this.^[10]

Related Research Articles

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

<span class="mw-page-title-main">Breadth-first search</span> Algorithm to search the nodes of a graph

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. However, in 2006 it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph $G$ , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In computer science, graph traversal refers to the process of visiting each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.

The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every induced subgraph of $n - 1$ vertices has a perfect matching.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length. The algorithm was conceived by John W. Suurballe and published in 1974. The main idea of Suurballe's algorithm is to use Dijkstra's algorithm to find one path, to modify the weights of the graph edges, and then to run Dijkstra's algorithm a second time. The output of the algorithm is formed by combining these two paths, discarding edges that are traversed in opposite directions by the paths, and using the remaining edges to form the two paths to return as the output. The modification to the weights is similar to the weight modification in Johnson's algorithm, and preserves the non-negativity of the weights while allowing the second instance of Dijkstra's algorithm to find the correct second path.

The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.

In graph theory, the Gallai–Edmonds decomposition is a partition of the vertices of a graph into three subsets which provides information on the structure of maximum matchings in the graph. Tibor Gallai and Jack Edmonds independently discovered it and proved its key properties.

In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.

References

↑ Edmonds, Jack (1991), "A glimpse of heaven", in J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver (eds.), History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland, Amsterdam, pp. 32–54
↑ Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi: 10.4153/CJM-1965-045-4 .
↑ Micali, Silvio; Vazirani, Vijay (1980). An O(V^1/2E) algorithm for finding maximum matching in general graphs. 21st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, New York. pp. 17–27.
↑ Edmonds, Jack (1965). "Maximum matching and a polyhedron with 0,1-vertices". Journal of Research of the National Bureau of Standards Section B. 69: 125–130. doi: 10.6028/jres.069B.013 .
↑ Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Berlin Heidelberg: Springer-Verlag. ISBN 9783540443896.
1 2 Lovász, László; Plummer, Michael (1986). Matching Theory. Akadémiai Kiadó. ISBN 963-05-4168-8.
1 2 Karp, Richard, "Edmonds's Non-Bipartite Matching Algorithm", Course Notes. U. C. Berkeley (PDF), archived from the original (PDF) on 2008-12-30
1 2 Tarjan, Robert, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching", Course Notes, Department of Computer Science, Princeton University (PDF)
↑ Kenyon, Claire; Lovász, László, "Algorithmic Discrete Mathematics", Technical Report CS-TR-251-90, Department of Computer Science, Princeton University
↑ Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Mathematical Programming Computation, 1 (1): 43–67, doi:10.1007/s12532-009-0002-8

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[glimpse-1] Edmonds, Jack (1991), "A glimpse of heaven", in J.K. Lenstra; A.H.G. Rinnooy Kan; A. Schrijver (eds.), History of Mathematical Programming --- A Collection of Personal Reminiscences, CWI, Amsterdam and North-Holland, Amsterdam, pp. 32–54

[algorithm-2] Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi: 10.4153/CJM-1965-045-4 .

[micali-3] Micali, Silvio; Vazirani, Vijay (1980). An O(V^1/2E) algorithm for finding maximum matching in general graphs. 21st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, New York. pp. 17–27.

[weighted-4] Edmonds, Jack (1965). "Maximum matching and a polyhedron with 0,1-vertices". Journal of Research of the National Bureau of Standards Section B. 69: 125–130. doi: 10.6028/jres.069B.013 .

[5] Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Berlin Heidelberg: Springer-Verlag. ISBN 9783540443896.

[matching_book-6] 1 2 Lovász, László; Plummer, Michael (1986). Matching Theory. Akadémiai Kiadó. ISBN 963-05-4168-8.

[karp_notes-7] 1 2 Karp, Richard, "Edmonds's Non-Bipartite Matching Algorithm", Course Notes. U. C. Berkeley (PDF), archived from the original (PDF) on 2008-12-30

[tarjan_notes-8] 1 2 Tarjan, Robert, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching", Course Notes, Department of Computer Science, Princeton University (PDF)

[kenyon_report-9] Kenyon, Claire; Lovász, László, "Algorithmic Discrete Mathematics", Technical Report CS-TR-251-90, Department of Computer Science, Princeton University

[blossom5-10] Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Mathematical Programming Computation, 1 (1): 43–67, doi:10.1007/s12532-009-0002-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]