Inapproximability of the independent set polynomial in the complex plane
DOI10.1137/18M1184485zbMATH Open1476.68193OpenAlexW3088330630MaRDI QIDQ5129229FDOQ5129229
Authors: Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, D. Štefankovič 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamics in One Complex Variable. (AM-160)
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Counting independent sets up to the tree threshold
- The roots of the independence polynomial of a clawfree graph
- NP is as easy as detecting unique solutions
- Counting in two-spin models on \(d\)-regular graphs
- An efficient algorithm for the complex roots problem
- Relative Distance--An Error Measure in Round-Off Error Analysis
- On a conjecture of Sokal concerning roots of the independence polynomial
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- The complexity of approximating complex-valued Ising and Tutte partition functions
- Title not available (Why is that?)
- Computing the independence polynomial: from the tree threshold down to the roots
Cited In (13)
- Implementations and the independent set polynomial below the Shearer threshold
- The complexity of approximating the complex-valued Potts model
- Inapproximability of the independent set polynomial in the complex plane
- The complexity of approximating the matching polynomial in the complex plane
- Absence of zeros implies strong spatial mixing
- On the zeroes of hypergraph independence polynomials
- On the location of chromatic zeros of series-parallel graphs
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- Computing the independence polynomial: from the tree threshold down to the roots
- The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
- Polylogarithmic inapproximability
- Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- Approximating the chromatic polynomial is as hard as computing it exactly
This page was built for publication: Inapproximability of the independent set polynomial in the complex plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5129229)
