Dulmage–Mendelsohn decomposition

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.[1] A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

Construction

The Dulmage-Mendelshon decomposition can be constructed as follows.[2] (it is attributed to [3] who in turn attribute it to [4]).

Let G be a bipartite graph, M a maximum-cardinality matching in G, and V0 the set of vertices of G unmatched by M (the "free vertices"). Then G can be partitioned into three parts:

The E-O-U decomposition
  • E - the even vertices - the vertices reachable from V0 by an M-alternating path of even length.
  • O - the odd vertices - the vertices reachable from V0 by an M-alternating path of odd length.
  • U - the unreachable vertices - the vertices unreachable from V0 by an M-alternating path.

An illustration is shown on the left. The bold lines are the edges of M. The weak lines are other edges of G. The red dots are the vertices of V0. Note that V0 is contained in E, since it is reachable from V0 by a path of length 0.

Based on this decomposition, the edges in G can be partitioned into six parts according to their endpoints: E-U, E-E, O-O, O-U, E-O, U-U. This decomposition has the following properties: [3]

  1. The sets E, O, U are pairwise-disjoint. Proof: U is disjoint from E and O by definition. To prove that E and O are disjoint, suppose that some vertex v has both an even-length alternating path to an unmatched vertex u1, and an odd-length alternating path to an unmatched vertex u2. Then, concatenating these two paths yields an augmenting path from u1 through v to u2. But this contradicts the assumption that M is a maximum-cardinality matching.
  2. The sets E, O, U do not depend on the maximum-cardinality matching M (i.e., any maximum-cardinality matching defines exactly the same decomposition).
  3. G contains only O-O, O-U, E-O and U-U edges.
  4. Any maximum-cardinality matching in G contains only E-O and U-U edges.
  5. Any maximum-cardinality matching in G saturates all vertices in O and all vertices in U.
  6. The size of a maximum-cardinality matching in G is |O| + |U| / 2.
  7. If G has a perfect matching, then all vertices of G are in U.

Alternative definition

The coarse decomposition

Let G = (X+Y,E) be a bipartite graph, and let D be the set of vertices in G that are not matched in at least one maximum matching of G. Then D is necessarily an independent set. So G can be partitioned into three parts:

  1. The vertices in D ∩ X and their neighbors;
  2. The vertices in D ∩ Y and their neighbors;
  3. The remaining vertices.

Every maximum matching in G consists of matchings in the first and second part that match all neighbors of D, together with a perfect matching of the remaining vertices. If G has a perfect matching, then the third set contains all vertices of G.

The fine decomposition

The third set of vertices in the coarse decomposition (or all vertices in a graph with a perfect matching) may additionally be partitioned into subsets by the following steps:

  • Find a perfect matching of G.
  • Form a directed graph H whose vertices are the matched edges in G. For each unmatched edge (x,y) in G, add a directed edge in H from the matched edge of x to the matched edge of y.
  • Find the strongly connected components of the resulting graph.
  • For each component of H, form a subset of the Dulmage–Mendelsohn decomposition consisting of the vertices in G that are endpoints of edges in the component.

To see that this subdivision into subsets characterizes the edges that belong to perfect matchings, suppose that two vertices x and y in G belong to the same subset of the decomposition, but are not already matched by the initial perfect matching. Then there exists a strongly connected component in H containing edge x,y. This edge must belong to a simple cycle in H (by the definition of strong connectivity) which necessarily corresponds to an alternating cycle in G (a cycle whose edges alternate between matched and unmatched edges). This alternating cycle may be used to modify the initial perfect matching to produce a new matching containing edge x,y.

An edge x,y of the graph G belongs to all perfect matchings of G, if and only if x and y are the only members of their set in the decomposition. Such an edge exists if and only if the matching preclusion number of the graph is one.

Core

As another component of the Dulmage–Mendelsohn decomposition, Dulmage and Mendelsohn defined the core of a graph to be the union of its maximum matchings.[5] However, this concept should be distinguished from the core in the sense of graph homomorphisms, and from the k-core formed by the removal of low-degree vertices.

Applications

This decomposition has been used to partition meshes in finite element analysis, and to determine specified, underspecified and overspecified equations in systems of nonlinear equations. It was also used for an algorithm for rank-maximal matching.

Asymmetric variant

In [6] there is a different decomposition of a bipartite graph, which is asymmetric - it distinguishes between vertices in one side of the graph and the vertices on the other side. It can be used to find a maximum-cardinality envy-free matching in an unweighted bipartite graph, as well as a minimum-cost maximum-cardinality matching in a weighted bipartite graph.[6]

References

  1. ^ Dulmage, A. L. & Mendelsohn, N. S. (1958). "Coverings of bipartite graphs". Can. J. Math. 10: 517–534. doi:10.4153/cjm-1958-052-0. The original Dulmage–Mendelsohn paper
  2. ^ "Dulmage Mendelsohn Decomposition" (PDF).
  3. ^ a b Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (2006-10-01). "Rank-maximal matchings". ACM Transactions on Algorithms. 2 (4): 602–610. doi:10.1145/1198513.1198520. S2CID 43243.
  4. ^ Pulleyblank, W.R. (1995). "Matchings and Extensions". Handbook of Combinatorics. Amsterdam, North-Holland: Elsevier Science. pp. 179–232.
  5. ^ Harary, Frank; Plummer, Michael D. (1967), "On the core of a graph", Proceedings of the London Mathematical Society, Third Series, 17: 305–314, doi:10.1112/plms/s3-17.2.305, hdl:2027.42/135576, MR 0209184.
  6. ^ a b Aigner-Horev, Elad; Segal-Halevi, Erel (2022-03-01). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv:1901.09527. doi:10.1016/j.ins.2021.11.059. ISSN 0020-0255. S2CID 170079201.
  • A good explanation of its application to systems of nonlinear equations is available in this paper: [1]
  • An open source implementation of the algorithm is available as a part of the sparse-matrix library: SPOOLES
  • Graph-theoretical aspects of constraint solving in the SST project: [2]