Name
Abstract | ||
|---|---|---|
Abstract. The coloured Tutte polynomial by Bollobás and Riordan is, as a generalisation of the Tutte polynomial, the most general graph polynomial for coloured graphs that satisfies certain contractiondeletion 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 establish this result in a proper way, we introduce a new kind of reductions, uniform algebraic reductions, that are well-suited to investigate the complexity of the evalua tion of graph polynomials. Our main result identifies a small, algebraic set of exceptional points, wit h the property that there exists a uniform algebraic reduction that reduces the evaluation problem,for the coloured Tutte polynomial,at any one non-exceptional point to any other non-exceptional point. On the way we also obtain a stronger result and a new,proof for the difficult evaluations in the com,plexity analysis for the classical Tutte polynomial. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-79709-8_12 | CSR |
Keywords | Field | DocType |
tutte polynomial,satisfiability | Alternating polynomial,Discrete mathematics,Combinatorics,Polynomial,Computer science,Tutte polynomial,Square-free polynomial,Monic polynomial,Reciprocal polynomial,Matrix polynomial,Wilkinson's polynomial | Conference |
Citations | PageRank | References |
5 | 0.47 | 17 |
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 |