zbMATH — the first resource for mathematics

Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions. (English) Zbl 1143.05023
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 86-98 (2008).
Summary: 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. F. Jaeger, D. L. Vertigan, and D. J. A. Welsh [“On the computational complexity of the Jones and Tutte polynomials”, Math. Proc. Camb. Philos. Soc. 108, No. 1, 35–53 (1990; Zbl 0747.57006)] 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.
For the entire collection see [Zbl 1136.68005].

05C15 Coloring of graphs and hypergraphs
57M15 Relations of low-dimensional topology with graph theory
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI