Matching

  

 

Input description: A (weighted) graph G=(V,E).

Problem description: Find the largest-size set of edges S from E such that each vertex in V is incident to at most one edge of S.

Discussion: Consider a set of employees, each of whom is capable of doing some subset of the tasks that must be performed.     We seek to find an assignment of employees to tasks such that each task is assigned to a unique employee.   Each mapping between an employee and a task they can handle defines an edge, so what we need is a set of edges with no employee or job in common, i.e. a matching.

Efficient algorithms for constructing matchings are based on constructing augmenting paths in graphs.   Given a (partial) matching M in a graph G, an augmenting path P is a path of edges where every odd-numbered edge (including the first and last edge) is not in M, while every even-numbered edge is. Further, the first and last vertices must not be already in M. By deleting the even-numbered edges of P from M and replacing them with the odd-numbered edges of P, we enlarge the size of the matching by one edge.   Berge's theorem states that a matching is maximum if and only if it does not contain any augmenting path.   Therefore, we can construct maximum-cardinality matchings by searching for augmenting paths and stopping when none exist.

This basic matching framework can be enhanced in several ways, while remaining essentially the same assignment problem:

• Is your graph weighted or unweighted? -   Many matching applications are based on unweighted graphs. Perhaps we seek to maximize the number of tasks performed, where each task is as good as another. Such a problem seeks a maximum cardinality matching.   We say that a matching is perfect if every vertex is involved in the matching.

  For certain applications, we need to augment each edge with a weight, perhaps reflecting the salary of the employee or their effectiveness at a given task. The problem now becomes constructing a maximum weighted matching, i.e. the set of independent edges of maximum total cost. By setting all edge weights to be 1, any algorithm for finding weighted matchings can be used to solve maximum cardinality matching.

• What if certain employees can be given multiple jobs? - In a natural generalization of the assignment problem, certain employees can given more than one task to do. We do not seek a matching so much as a covering with small ``stars''. Such multiple jobs can be modeled by simply replicating the employee vertex as many times as the number of jobs she can handle. By adding sufficiently complicated constraints on the solution, we will eventually require the use of full integer programming.
• Is your graph bipartite? -   Many common matching problems involve bipartite graphs, as in the classical assignment problem of jobs to workers. This is fortunate because faster and simpler algorithms exist for bipartite matching. General graphs prove trickier because it is possible to have augmenting paths that are odd-length cycles, i.e. the first and last vertices are the same.   Such cycles (or blossoms) are impossible in bipartite graphs, which by definition do not contain odd-length cycles.   

  The standard algorithms for bipartite matching are based on network flow, using a simple transformation to convert a bipartite graph into an equivalent flow graph.

Another common ``application'' of bipartite matching is in marrying off a set of boys to a set of girls such that each boy gets   a girl he likes. This can be modeled as a bipartite matching problem, with an edge between any compatible boy and girl. This is possible only for graphs with perfect matchings. An interesting related problem seeks a matching such that no parties can be unhappy enough to seek to break the matching. That is, once each of the boys has ranked each of the girls in terms of desirability, and the girls do the same to the boys, we seek a matching with the property that there are no marriages of the form and , where and in fact prefer each other to their own spouses. In real life, these two would run off with each other, breaking the marriages.   A marriage without any such couples is said to be stable.

It is a surprising fact that no matter how the boys and girls rate each other, there is always at least one stable marriage. Further, such a marriage can be found in time.   An important application of stable marriage occurs in the annual matching of medical residents to hospitals.

Implementations: The highest performance code available for constructing a maximum-cardinality bipartite matching of maximum weight in graphs is CSA [GK93], developed in the C language by Goldberg and Kennedy. This code is based on a cost-scaling network flow algorithm. They report solving instances with over 30,000 vertices in a few minutes on a Sun Sparc-2 workstation. Their codes are available for noncommercial use from http://www.neci.nj.nec.com/homepages/avg.html   

The First DIMACS Implementation Challenge [JM93] focused on network flows and matching.   Several instance generators and implementations for maximum weight and maximum cardinality matching were collected, which can be obtained by anonymous ftp from dimacs.rutgers.edu in the directory pub/netflow/matching. These include:

• A maximum-cardinality matching solver in Fortran 77 by R. Bruce Mattingly and Nathan P. Ritchey that seems capable of solving   instances of 5,000 nodes and 60,000 edges in under 30 seconds.
• A maximum-cardinality matching solver in C by Edward Rothberg, that implements Gabow's algorithm.
• A maximum-weighted matching solver in C by Edward Rothberg. This is slower but more general than his unweighted solver described above. For example, it took over 30 seconds on a weighted graph with 500 nodes and 4,000 edges.

LEDA (see Section ) provides efficient implementations in C++ for both maximum cardinality and maximum weighted matching, on both bipartite and general graphs.     Sedgewick [Sed92] provides a simple implementation of the stable marriage theorem in C++. See Section for details.

Pascal implementations of maximum cardinality matching appears in [SDK83].   Alternative Pascal maximum-cardinality and bipartite matching codes appear in [MS91]. All are discussed in Section .

The Stanford GraphBase (see Section ) contains an implementation of the Hungarian algorithm for bipartite matching. To provide readily visualized weighted bipartite graphs, Knuth uses a digitized version of the Mona Lisa and seeks row/column disjoint pixels of maximum brightness. Matching is also used to construct clever, resampled ``domino portraits.''    

Algorithm 548 [CT80] presents a Fortran code for the assignment problem. Algorithm 575 [Duf81] permutes a matrix so as to minimize the number of zeros along the diagonal, which involves solving a matching problem. Both codes are available from Netlib (see Section ).    

    Combinatorica [Ski90] provides a (slow) Mathematica implementations of bipartite and maximal matching, as well as the stable marriage theorem. See Section .

Notes: Lovász and Plummer [LP86] is the definitive reference on matching theory and algorithms. Survey articles on matching algorithms include [Gal86]. Good expositions on network flow algorithms for bipartite matching include [CLR90, Eve79a, Man89], and those on the Hungarian method include [Law76, PS82]. The best algorithm for maximum bipartite matching, due to Hopcroft and Karp [HK73], repeatedly finds the shortest augmenting paths instead of using network flow, and runs in . Expositions on the augmenting path method include [Man89, PS82, SDK83].

Edmond's algorithm [Edm65] for maximum-cardinality matching   is of great historical interest for provoking questions about what problems can be solved in polynomial time. Expositions on Edmond's algorithm include [Law76, PS82, Tar83]. Gabow's [Gab76] implementation of Edmond's algorithm runs in time. The best algorithm known for general matching runs in [MV80].   A faster algorithm for matching in geometic graphs appears in [Vai88].

The theory of stable matching is thoroughly treated in [GI89].   The original algorithm for finding stable marriages is due to Gale and Shapely [GS62] with expositions including [Law76].

Related Problems: Eulerian cycle (see page ), network flow (see page ).