Matroid matching

From Egres Open
Jump to: navigation, search

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

  1. P. Jensen, B. Korte, Complexity of matroid property algorithms, SIAM J. Comput. 11 (1982), 184–190, DOI link.
  2. L. Lovász, Selecting independent lines from a family of lines in a space, Acta Sci. Math. 42 (1980), 121–131.
  3. 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.
  4. L. Lovász, Matroid matching and some applications, DOI link
  5. H.N. Gabow, N. Stallmann, An augmenting path algorithm for linear matroid parity, DOI link
  6. J.B. Orlin, J.H. Vande Vate, Solving the linear matroid parity problem as a sequence of matroid intersection problems, DOI link
  7. H.Y. Cheung, L.C. Lau, K.M. Leung, Algebraic algorithms for linear matroid parity problems, DOI link, author link
  8. J.F. Geelen, S. Iwata, K. Murota, The linear delta-matroid parity problem, DOI link, author link
  9. J.F. Geelen, S. Iwata, Matroid matching via mixed skew-symmetric matrices, DOI link, author link
  10. M. Makai, Parity problems of combinatorial polymatroids, Ph.D. Thesis, ELTE, 2009, PDF link