Inapproximability of the independent set polynomial in the complex plane

DOI10.1145/3188745.3188788zbMath1427.68229arXiv1711.00282OpenAlexW2964131987MaRDI QIDQ5230376

Daniel Štefanković, Andreas Galanis, Ivona Bezáková, Leslie Ann Goldberg

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

inapproximabilityindependent set polynomial\(\#\)P-hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

A Spectral Independence View on Hard Spheres via Block Dynamics ⋮ Algorithmic Pirogov-Sinai theory ⋮ Location of zeros for the partition function of the Ising model on bounded degree graphs ⋮ Cayley trees do not determine the maximal zero-free locus of the independence polynomial ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On a conjecture of Sokal concerning roots of the independence polynomial ⋮ The complexity of approximating the complex-valued Potts model

This page was built for publication: Inapproximability of the independent set polynomial in the complex plane