The linear delta-matroid parity problem

This paper addresses a generalization of the matroid parity problem to delta-matroids. We give a minimax relation, as well as an efficient algorithm, for linearly represented delta-matroids. These are natural extensions of the minimax theorem of Lovلsz and the augmenting path algorithm of Gabow and Stallmann for the linear matroid parity problem.