# Matroid matching

Let *M=(V,r)* be a matroid, and let *G=(V,E)* be a graph. The **matroid matching problem** is to find a matching [math]F \subseteq E[/math] of maximum cardinality for which *V(F)* is independent in *M*. If *M* is the free matroid, then we obtain the maximum matching problem. Other special cases include the minimum pinning set problem and Mader's disjoint S-paths problem.

It can be assumed w.l.o.g. that *G* is a collection of independent edges, since the structure of *G* can be encoded in the matroid. This version is usually called the **matroid parity problem**.

In general, the matroid matching problem is hard: it may require an exponential number of oracle calls ^{[1]}. Lovász ^{[2]}^{[3]}^{[4]} gave a min-max formula and a polynomial algorithm for matroid matching in linearly represented matroids. More efficient deterministic algorithms have been found by Gabow and Stallmann ^{[5]} and Orlin and Vande Vate ^{[6]}, while Cheung, Lau and Leung ^{[7]} developed fast randomized algorithms.

The Lovász formula and the Gabow-Stallmann algorithm were extended to the linear delta-matroid parity problem by Geelen, Iwata, and Murota ^{[8]}^{[9]}. Additional results on matroid matching problems involving combinatorially defined matroids can be found in the thesis of Makai ^{[10]}.

## References

- ↑ P. Jensen, B. Korte,
*Complexity of matroid property algorithms*, SIAM J. Comput. 11 (1982), 184–190, DOI link. - ↑ L. Lovász,
*Selecting independent lines from a family of lines in a space*, Acta Sci. Math. 42 (1980), 121–131. - ↑ L. Lovász,
*The matroid matching problem*, in: Algebraic methods in graph theory (Szeged, 1978), Colloq. Math. Soc. János Bolyai 25 (1981), 495–517. - ↑ L. Lovász,
*Matroid matching and some applications*, DOI link - ↑ H.N. Gabow, N. Stallmann,
*An augmenting path algorithm for linear matroid parity*, DOI link - ↑ J.B. Orlin, J.H. Vande Vate,
*Solving the linear matroid parity problem as a sequence of matroid intersection problems*, DOI link - ↑ H.Y. Cheung, L.C. Lau, K.M. Leung,
*Algebraic algorithms for linear matroid parity problems*, DOI link, author link - ↑ J.F. Geelen, S. Iwata, K. Murota,
*The linear delta-matroid parity problem*, DOI link, author link - ↑ J.F. Geelen, S. Iwata,
*Matroid matching via mixed skew-symmetric matrices*, DOI link, author link - ↑ M. Makai,
*Parity problems of combinatorial polymatroids*, Ph.D. Thesis, ELTE, 2009, PDF link