In this paper, the authors present an O(r4n) algorithm for the linear matroid parity problem. The present solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important sublcass of non-simple parity problems called ‘easy’ parity problems which can be solved as matroid intersection problems. The authors then show how to solve any linear matroid parity problem parametrically as a sequence of ‘easy’ parity problems. In contrast to other algorithmic work on this problem, they focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, the authors develop these ideas into a duality theory for the parity problem.
