next up previous contents index CD CD Algorithms
Next: Eulerian Cycle / Chinese Up: Graph Problems: Polynomial-Time Previous: Transitive Closure and Reduction




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:

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 tex2html_wrap_inline28887 and tex2html_wrap_inline28889 , where tex2html_wrap_inline28891 and tex2html_wrap_inline28893 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 tex2html_wrap_inline28895 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   

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 in the directory pub/netflow/matching. These include:

LEDA (see Section gif) 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 gif 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 gif.

The Stanford GraphBase (see Section gif) 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 gif).    

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

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 tex2html_wrap_inline28899 . 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 tex2html_wrap_inline28901 time. The best algorithm known for general matching runs in tex2html_wrap_inline28903 [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 gif), network flow (see page gif).    

next up previous contents index CD CD Algorithms
Next: Eulerian Cycle / Chinese Up: Graph Problems: Polynomial-Time Previous: Transitive Closure and Reduction

Mon Jun 2 23:33:50 EDT 1997