New algorithms for linear k -matroid intersection and matroid k -parity problems

Abstract

We present algorithms for the k -Matroid Intersection Problem and for the Matroid k -Parity Problem when the matroids are represented over the field of rational numbers and k > 2. The computational complexity of the algorithms is linear in the cardinality and singly exponential in the rank of the matroids. As an application, we describe new polynomially solvable cases of the k -Dimensional Assignment Problem and of the k -Dimensional Matching Problem. The algorithms use some new identities in multilinear algebra including the generalized Binet—Cauchy formula and its analogue for the Pfaffian. These techniques extend known methods developed earlier for k = 2.