Mark Jerrum (Edinburgh): Inapproximability of the Tutte polynomial
The (classical) Tutte polynomial of a graph G
is a two-variable polynomial T(G;x,y) that encodes
much information about G. The number of spanning trees in G,
the number of acyclic orientations of G and the partition
function of the q-state Potts model are all specialisations
of the Tutte polynomial. From a complexity-theoretic point
of view, "mapping the Tutte plane" amounts to determining
the computational complexity of evaluating T(G;x,y), given G,
for each rational pair (x,y). For exact computation,
the mapping was done in detail by Jaeger, Vertigan and Welsh.
For approximate computation (within specified relative error)
much less was known. I'll report on recent work with Leslie
Goldberg (Liverpool) that makes some progress in this direction.