Solving the linear matroid parity problem as a sequence of matroid intersection problems (Q1813836)

The authors present an \(O(r^ 4 n)\) algorithm for the following linear matroid parity problem. Let \(A\) be an \(r\times 2n\) matrix over a field \(F\) with columns partitioned into pairs \(A(1),\dots, A(n)\). Find a collection \(A(i_ 1),\dots, A(i_ k)\) of maximal cardinality \(k\) consisting of linearly independent columns. This problem is imbedded into a wider class of optimization problems where \(\text{card }A(i_ j)\) is not necessarily equal to 2 and then is replaced by a sequence of so- called ``easy parity problems'' each of which can be solved as a matroid intersection problem. By certain duality results it follows that one can indeed obtain an optimal solution of the initial problem. Some connections with graphic matching problems are considered.