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.
Classification :
05C31, 68Q17, 05B35
Mots-clés :
computational complexity, counting bases of a binary matroid
Affiliations des auteurs :
Christopher Knapp
1
;
Steven Noble
2
1
Brunel University
2
University of Leeds
Christopher Knapp; Steven Noble. The complexity of the greedoid Tutte polynomial. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/11718
@article{10_37236_11718,
author = {Christopher Knapp and Steven Noble},
title = {The complexity of the greedoid {Tutte} polynomial},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {3},
doi = {10.37236/11718},
zbl = {8097631},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11718/}
}
TY - JOUR
AU - Christopher Knapp
AU - Steven Noble
TI - The complexity of the greedoid Tutte polynomial
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/11718/
DO - 10.37236/11718
ID - 10_37236_11718
ER -
%0 Journal Article
%A Christopher Knapp
%A Steven Noble
%T The complexity of the greedoid Tutte polynomial
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11718/
%R 10.37236/11718
%F 10_37236_11718
