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.

An illustration of the three sets in the Gallai–Edmonds decomposition of an example graph.

The Gallai–Edmonds decomposition of a graph can be found using the blossom algorithm.

Properties

edit

Given a graph  , its Gallai–Edmonds decomposition consists of three disjoint sets of vertices,  ,  , and  , whose union is  : the set of all vertices of  . First, the vertices of   are divided into essential vertices (vertices which are covered by every maximum matching in  ) and inessential vertices (vertices which are left uncovered by at least one maximum matching in  ). The set   is defined to contain all the inessential vertices. Essential vertices are split into   and  : the set   is defined to contain all essential vertices adjacent to at least one vertex of  , and   is defined to contain all essential vertices not adjacent to any vertices of  .[4]

It is common to identify the sets  ,  , and   with the subgraphs induced by those sets. For example, we say "the components of  " to mean the connected components of the subgraph induced by  .

The Gallai–Edmonds decomposition has the following properties:[5]

  1. The components of   are factor-critical graphs: each component has an odd number of vertices, and when any one of these vertices is left out, there is a perfect matching of the remaining vertices. In particular, each component has a near-perfect matching: a matching that covers all but one of the vertices.
  2. The subgraph induced by   has a perfect matching.
  3. Every non-empty subset   has neighbors in at least   components of  .
  4. Every maximum matching in   has the following structure: it consists of a near-perfect matching of each component of  , a perfect matching of  , and edges from all vertices in   to distinct components of  .
  5. If   has   components, then the number of edges in any maximum matching in   is  .

Construction

edit

The Gallai–Edmonds decomposition of a graph   can be found, somewhat inefficiently, by starting with any algorithm for finding a maximum matching. From the definition, a vertex   is in   if and only if   (the graph obtained from   by deleting  ) has a maximum matching of the same size as  . Therefore we can identify   by computing a maximum matching in   and in   for every vertex  . The complement of   can be partitioned into   and   directly from the definition.

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:

  1. All vertices of a blossom are inessential vertices of the bigger graph.
  2. The vertex formed by contracting the blossom is an inessential vertex of the smaller graph.

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]

Let   be a graph,   a matching in  , and let   be a cycle of length  which contains   edges of   and is vertex-disjoint from the rest of  . Construct a new graph   from   by shrinking   to a single vertex. Then   is a maximum matching in   if and only if   is a maximum matching in  .

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  , a maximum matching   in   of the same size as  , and an alternating forest   in   with respect to  . In  , the Gallai–Edmonds decomposition has a short description. The vertices in   are classified into inner vertices (vertices at an odd distance in   from a root) and outer vertices (vertices at an even distance in   from a root);   is exactly the set of inner vertices, and   is exactly the set of outer vertices. Vertices of   that are not in   form  .[7]

Contracting blossoms preserves the set of inessential vertices; therefore   can be found from   by taking all vertices of   which were contracted as part of a blossom, as well as all vertices in  . The vertices in   and   are never contracted;   and  .

Generalizations

edit

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".[9]

References

edit
  1. ^ Gallai, Tibor (1963), "Kritische graphen II", Magyar Tud. Akad. Mat. Kutato Int. Kozl., 8: 373–395
  2. ^ Gallai, Tibor (1964), "Maximale Systeme unabhängiger Kanten", Magyar Tud. Akad. Mat. Kutato Int. Kozl., 9: 401–413
  3. ^ Edmonds, Jack (1965), "Paths, trees, and flowers", Canadian Journal of Mathematics, 17: 449–467, doi:10.4153/CJM-1965-045-4, S2CID 18909734
  4. ^ Lovász, László; Plummer, Michael D. (1986), Matching Theory (1st ed.), North-Holland, Section 3.2, ISBN 978-0-8218-4759-6
  5. ^ Theorem 3.2.1 in Lovász and Plummer, p. 94
  6. ^ Lemma 9.1.1 in Lovász and Plummer, p. 358
  7. ^ Exercise 9.1.2 in Lovász and Plummer, p. 360
  8. ^ Szabó, Jácint; Loebl, Martin; Janata, Marek (14 February 2005), "The Edmonds–Gallai Decomposition for the k-Piece Packing Problem", The Electronic Journal of Combinatorics, 12, doi:10.37236/1905, S2CID 11992200
  9. ^ Paluch, Katarzyna (22 May 2013), "Capacitated Rank-Maximal Matchings", Algorithms and Complexity, Lecture Notes in Computer Science, vol. 7878, Springer, Berlin, Heidelberg, pp. 324–335, doi:10.1007/978-3-642-38233-8_27, ISBN 978-3-642-38232-1