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
