Computing the independence polynomial: from the tree threshold down to the roots

zbMATH Open1403.68351arXiv1608.02282MaRDI QIDQ4607991FDOQ4607991

Authors: Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák 

Publication date: 15 March 2018

Abstract: We study an algorithm for approximating the multivariate independence polynomial $Z(mathbfz)$, with negative and complex arguments, an object that has strong connections to combinatorics and to statistical physics. In particular, the independence polynomial with negative arguments, $Z(-mathbfp)$, determines the Shearer region, the maximal region of probabilities to which the Lovasz Local Lemma (LLL) can be extended (Shearer 1985). In statistical physics, complex zeros of the independence polynomial relate to existence of phase transitions. Our main result is a deterministic algorithm to compute approximately the independence polynomial in any root-free complex polydisc centered at the origin. Our algorithm is essentially the same as Weitz's algorithm for positive parameters up to the tree uniqueness threshold, and the core of our analysis is a novel multivariate form of the correlation decay technique, which can handle non-uniform complex parameters. In particular, in the univariate real setting our work implies that Weitz's algorithm works in an interval between two critical points $(lambda{\text{'}}_c(d),lambd{a}_c(d))$, and outside of this interval an approximation of $Z(mathbfz)$ is known to be NP-hard. As an application, we give a sub-exponential time algorithm for testing approximate membership in the Shearer region. We also give a new rounding based deterministic algorithm for Shearer's lemma (an extension of the LLL), which, however, runs in sub-exponential time. On the hardness side, we prove that evaluating $Z(mathbfz)$ at an arbitrary point in Shearer's region, and testing membership in Shearer's region, are #P-hard problems. We also establish the best possible dependence of the exponent of the run time of Weitz's correlation decay technique in the negative regime on the distance to the boundary of the Shearer region.

Full work available at URL: https://arxiv.org/abs/1608.02282

Recommendations

• scientific article; zbMATH DE number 7204480
• Implementations and the independent set polynomial below the Shearer threshold
• Inapproximability of the independent set polynomial in the complex plane
• Inapproximability of the independent set polynomial in the complex plane
• Counting independent sets up to the tree threshold

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms (68W40) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (16)

• Implementations and the independent set polynomial below the Shearer threshold
• A spectral independence view on hard spheres via block dynamics
• Title not available (Why is that?)
• Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
• The complexity of approximating the matching polynomial in the complex plane
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• On the zeroes of hypergraph independence polynomials
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• Dynamic Sampling from Graphical Models
• Correlation decay and the absence of zeros property of partition functions
• Inapproximability of the independent set polynomial in the complex plane
• Algorithmic Pirogov-Sinai theory
• Counting independent sets in graphs with bounded bipartite pathwidth
• Fisher zeros and correlation decay in the Ising model
• Fisher Zeros and Correlation Decay in the Ising Model
• Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems

This page was built for publication: Computing the independence polynomial: from the tree threshold down to the roots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607991)