Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Viresh Patel, Guus Regts

Published 2016-07-05Version 1

In this paper we give the first deterministic polynomial-time approximation algorithm for computing complex-valued evaluations of the Tutte polynomial and the independence polynomial on bounded degree graphs, as well for computing partition functions of complex-valued spin and edge-coloring models on bounded degree graphs. Our work builds on a recent line of work initiated by Barvinok (A. Barvinok, Computing the permanent of (some) complex matrices, Foundations of Computational Mathematics (2014) 1-14. A. Barvinok, Computing the partition function for cliques in a graph, Theory of Computing 11 (2015), Article 13 pp. 339-355), which provides a new algorithmic approach besides the existing correlation decay method for these types of problems.