Edmonds' matroid intersection theorem
From Egres Open
Theorem (Edmonds [1]). Let [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math] be two matroids. Then the maximum size of a common independent set of [math]M_1[/math] and [math]M_2[/math] is [math]\min_{X \subseteq S} (r_1(X)+r_2(S \setminus X)).[/math]
This can be derived from Matroid union theorem, and vice versa. There are several efficient algorithms for finding a maximum size common independent set: Cunningham [2] gave an algorithm that needs [math]O(n r^{1.5})[/math] oracle calls, and Harvey [3] presented a randomized algorithm for linear matroids with running time [math]O(nr^{\omega-1})[/math], where r is the rank and [math]\omega[/math] is the matrix multiplication exponent.
References
- ↑ J. Edmonds, Submodular functions, matroids, and certain polyhedra, In: R. Guy, H. Hanani, N. Sauer and J. Schönheim, Editors, Combinatorial Structures and Their Applications, Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, Alberta, June 1969, Gordon and Breach, New York (1970), pp. 69–87. DOI link (LNCS version).
- ↑ W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms, DOI link.
- ↑ N. J. A. Harvey, Algebraic algorithms for matching and matroid problems, DOI link.
