Complexity of the Bollobás–Riordan Polynomial Exc

Authors: Markus Bläser Holger Dell Johann A Makowsky

Publish Date: 2009/05/15

Volume: 46, Issue: 4, Pages: 690-706

PDF Link

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 contractiondeletion identities Jaeger Vertigan and Welsh showed that the classical Tutte polynomial is Phard to evaluate almost everywhere by establishing reductions along curves and linesWe 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 wellsuited 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 nonexceptional points under polynomialtime uniform algebraic reductions On the way we obtain a selfcontained proof for the difficult evaluations of the classical Tutte polynomial

Keywords: