Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T19:06:01.574Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids

Published online by Cambridge University Press:  07 April 2006

OMER GIMÉNEZ  and
MARC NOY
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])
Get access Rights & Permissions [Opens in a new window]

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
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 3 , May 2006 , pp. 385 - 395
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.)