The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersxandy. It is shown that for fixedxandythe problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersxandysatisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.