Inapproximability of the Independent Set Polynomial in the Complex Plane

DOI10.1137/18M1184485zbMath1476.68193OpenAlexW3088330630MaRDI QIDQ5129229

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

Publication date: 26 October 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1184485

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

The complexity of approximating the complex-valued Potts model ⋮ Absence of zeros implies strong spatial mixing ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ On the location of chromatic zeros of series-parallel graphs ⋮ Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial ⋮ The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs ⋮ Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Counting in two-spin models on \(d\)-regular graphs
• The roots of the independence polynomial of a clawfree graph
• NP is as easy as detecting unique solutions
• The complexity of approximating complex-valued Ising and Tutte partition functions
• On a conjecture of Sokal concerning roots of the independence polynomial
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• An efficient algorithm for the complex roots problem
• Counting independent sets up to the tree threshold
• Relative Distance--An Error Measure in Round-Off Error Analysis
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Dynamics in One Complex Variable. (AM-160)
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Inapproximability of the Independent Set Polynomial in the Complex Plane