Maximum Matching (MM)
Input
An undirected graph $G = (V, E)$.
Problem
Find a maximum matching of $G$.
Definitions
A matching is a subset of edges that share no endpoints. A matching is maximum if no matching of larger cardinality exists.
Status
Open (Feather [1], Karp, Upfal, and Wigderson [2], Mulmuley, Vazirani, and Vazirani [3]).
Remarks
Feather shows that the problem of finding the size of a maximum matching is in $\mathsf{RNC}$ [1]. Karp, Upfal, and Wigderson gave the first $\mathsf{RNC}$ algorithm for finding the maximum matching [2]. A more efficient algorithm was given by Mulmuley, Vazirani, and Vazirani [3].
Karloff shows how any $\mathsf{RNC}$ algorithm for matching can be made errorless [4]. Maximum Edge-weighted Matching for unary edge weights and Maximum Vertex-weighted Matching for binary vertex weights are also known to be in $\mathsf{RNC}$ [2][3]. See also PME.
References
- T. Feather (1984). The parallel complexity of some flow and matching problems.
- R. M. Karp, E. Upfal, and A. Wigderson (1986). Constructing a perfect matching is in Random NC.
- K. Mulmuley, U. V. Vazirani, and V. V. Vazirani (1987). Matching is as easy as matrix inversion.
- H. J. Karloff (1986). A Las Vegas RNC algorithm for maximum matching.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.9.7.