期刊
SIAM JOURNAL ON COMPUTING
卷 46, 期 6, 页码 1893-1919出版社
SIAM PUBLICATIONS
DOI: 10.1137/16M1101003
关键词
approximation algorithms; Tutte polynomial; independence polynomial; partition function; graph homomorphism; Holant problem
资金
- Netherlands Organisation for Scientific Research (NWO) through the Gravitation Programme Networks [024.002.003]
- NWO Veni grant
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据