Algebraic Structures and Algorithms for Matching and Matroid Problems

We present new algebraic approaches for several well-known combinatorial problems, including non-bipartite matching, matroid intersection, and some of their generalizations. Our work yields new randomized algorithms that are the most efficient known. For non-bipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n^w) where n is the number of vertices and w is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time O(nr^{w - 1})for matroids with n elements and rank r that satisfy some natural conditions. This algorithm is based on new algebraic results characterizing the size of a maximum intersection in contracted matroids. Furthermore, the running time of this algorithm is essentially optimal