Gallai–Edmonds decomposition
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[1][2] and Jack Edmonds[3] independently discovered it and proved its key properties.
The Gallai–Edmonds decomposition of a graph can be found using the blossom algorithm.
, its Gallai–Edmonds decomposition consists of three disjoint sets of vertices,
) and inessential vertices (vertices which are left uncovered by at least one maximum matching in
is defined to contain all the inessential vertices.
Essential vertices are split into
is defined to contain all essential vertices adjacent to at least one vertex of
[4] It is common to identify the sets
with the subgraphs induced by those sets.
" to mean the connected components of the subgraph induced by
can be found, somewhat inefficiently, by starting with any algorithm for finding a maximum matching.
) has a maximum matching of the same size as
by computing a maximum matching in
One particular method for finding a maximum matching in a graph is Edmonds' blossom algorithm, and the processing done by this algorithm enables us to find the Gallai–Edmonds decomposition directly.
To find a maximum matching in a graph
, the blossom algorithm starts with a small matching and goes through multiple iterations in which it increases the size of the matching by one edge.
We can find the Gallai–Edmonds decomposition from the blossom algorithm's work in the last iteration: the work done when it has a maximum matching
, which it fails to make any larger.
In every iteration, the blossom algorithm passes from
to smaller graphs by contracting subgraphs called "blossoms" to single vertices.
When this is done in the last iteration, the blossoms have a special property: The first property follows from the algorithm: every vertex of a blossom is the endpoint of an alternating path that starts at a vertex uncovered by the matching.
The second property follows from the first by the lemma below:[6] This lemma also implies that when a blossom is contracted, the set of inessential vertices outside the blossom remains the same.
Once every blossom has been contracted by the algorithm, the result is a smaller graph
, the Gallai–Edmonds decomposition has a short description.
is exactly the set of outer vertices.
[7] Contracting blossoms preserves the set of inessential vertices; therefore
which were contracted as part of a blossom, as well as all vertices in
The Gallai–Edmonds decomposition is a generalization of Dulmage–Mendelsohn decomposition from bipartite graphs to general graphs.
[8] An extension of the Gallai–Edmonds decomposition theorem to multi-edge matchings is given in Katarzyna Paluch's "Capacitated Rank-Maximal Matchings".
