Name
Title | ||
|---|---|---|
Complexity of the Bollobás–Riordan Polynomial. Exceptional Points and Uniform Reductions |
Abstract | ||
|---|---|---|
The coloured Tutte polynomial by Bollobás and Riordan is, as a generalization of the Tutte polynomial, the most general graph polynomial for coloured graphs that satisfies certain contraction-deletion identities. Jaeger, Vertigan, and Welsh showed that the classical Tutte polynomial is #P-hard to evaluate almost everywhere by establishing reductions along curves and lines. We establish a similar result for the coloured Tutte polynomial on integral domains. To capture the algebraic flavour and the uniformity inherent in this type of result, we introduce a new kind of reductions, uniform algebraic reductions, that are well-suited to investigate the evaluation complexity of graph polynomials. Our main result identifies a small, algebraic set of exceptional points and says that the evaluation problem of the coloured Tutte is equivalent for all non-exceptional points, under polynomial-time uniform algebraic reductions. On the way we obtain a self-contained proof for the difficult evaluations of the classical Tutte polynomial. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00224-009-9213-7 | Theory of Computing Systems - Special Issue: Symposium on Computer Science; Guest Editors: Sergei Artemov, Volker Diekert and Alexander Razborov |
Keywords | DocType | Volume |
Computational complexity,Tutte polynomial,Graph polynomials,Algebraic reductions | Journal | 46 |
Issue | ISSN | ISBN |
4 | 1432-4350 | 3-540-79708-4 |
Citations | PageRank | References |
5 | 0.50 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Bläser | 1 | 326 | 34.03 |
| Holger Dell | 2 | 220 | 16.74 |
| Johann A. Makowsky | 3 | 509 | 130.82 |