Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-29T08:00:44.896Z Has data issue: false hasContentIssue false

On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids

Published online by Cambridge University Press:  07 April 2006

OMER GIMÉNEZ
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, Spain (e-mail: [email protected], [email protected])
MARC NOY
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, Spain (e-mail: [email protected], [email protected])

Abstract

We show that evaluating the Tutte polynomial for the class of bicircular matroids is #P-hard at every point $(x,y)$ except those in the hyperbola $(x-1)(y-1)=1$ and possibly those on the lines $x=0$ and $x=-1$. Since bicircular matroids form a rather restricted subclass of transversal matroids, our results can be seen as a partial strengthening of a result by Colbourn, Provan and Vertigan, namely that the evaluation of the Tutte polynomial for the class of transversal matroids is #P-hard for all points except those in the hyperbola $(x-1)(y-1)=1$.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)