Computing the Independence Polynomial: from the Tree Threshold down to the Roots

zbMath1403.68351arXiv1608.02282MaRDI QIDQ4607991

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

Publication date: 15 March 2018

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

Mathematics Subject Classification ID

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

Related Items (15)

A Spectral Independence View on Hard Spheres via Block Dynamics ⋮ Algorithmic Pirogov-Sinai theory ⋮ Correlation decay and the absence of zeros property of partition functions ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Inapproximability of the Independent Set Polynomial in the Complex Plane ⋮ On the zeroes of hypergraph independence polynomials ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fisher zeros and correlation decay in the Ising model ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ Fisher Zeros and Correlation Decay in the Ising Model ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ Dynamic Sampling from Graphical Models ⋮ Implementations and the independent set polynomial below the Shearer threshold

This page was built for publication: Computing the Independence Polynomial: from the Tree Threshold down to the Roots