DETERMINISTIC POLYNOMIAL-TIME APPROXIMATION ALGORITHMS FOR PARTITION FUNCTIONS AND GRAPH POLYNOMIALS

摘要

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More speci fi cally, we de fi ne a large class of graph polynomials C and show that if p is an element of C and there is a disk D centered at zero in the complex plane such that p (G) does not vanish on D for all bounded degree graphs G, then for each z in the interior of D there exists a deterministic polynomialtime approximation algorithm for evaluating p (G) at z. This gives an explicit connection between absence of zeros of graph polynomials and the existence of e ffi cient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated by Barvinok [Found. Comput. Math., 16 (2016), pp. 329-342; Theory Comput., 11 (2015), pp. 339-355; Computing the Partition Function of a Polynomial on the Boolean Cube, 2015; Discrete Anal., 2 (2017), 34pp], which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems.