The Complexity of the Greedoid Tutte Polynomial

Abstract

We consider the Tutte polynomial of three classes of greedoids: those arising from rooted graphs, rooted digraphs and binary matrices. We establish the computational complexity of evaluating each of these polynomials at each fixed rational point $(x,y)$. In each case we show that evaluation is $\#$P-hard except for a small number of exceptional cases when there is a polynomial time algorithm. In the binary case, establishing $\#$P-hardness along one line relies on Vertigan's unpublished result on the complexity of counting bases of a binary matroid. For completeness, we include an appendix providing a proof of this result.