Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T17:08:52.313Z 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: omer.gimenez@upc.es, marc.noy@upc.es)
MARC NOY
Affiliation:
Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, Spain (e-mail: omer.gimenez@upc.es, marc.noy@upc.es)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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$.

Information

Type
Paper
Copyright
2006 Cambridge University Press