Contracting a Single Element in a Transversal Matroid

Abstract

It is well known that the class of transversal matroids is not closed under contraction or duality. In particular, after contracting a set of elements from a transversal matroid, the resulting matroid may or may not be transversal, and the computational complexity of determining whether it is transversal is not well understood. As a step toward resolving this, we provide a polynomial-time algorithm for determining whether a single-element contraction of a transversal matroid is transversal. In the case that the single-element contraction is transversal, the algorithm also provides a transversal representation. We then discuss possible applications of our techniques toward finding a polynomial-time algorithm to determine if the dual of a transversal matroid is transversal.

31 pages