Inapproximability of the independent set polynomial in the complex plane

DOI10.1137/18M1184485MaRDI QIDQ5129229zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

inapproximabilityindependent set polynomial\#P-hardness

Mathematics Subject Classification ID

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 51680 (Why is no real title available?)
• scientific article; zbMATH DE number 2120364 (Why is no real title available?)
• scientific article; zbMATH DE number 7204480 (Why is no real title available?)
• An efficient algorithm for the complex roots problem
• Computing the independence polynomial: from the tree threshold down to the roots
• Counting in two-spin models on \(d\)-regular graphs
• Counting independent sets up to the tree threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Dynamics in One Complex Variable. (AM-160)
• NP is as easy as detecting unique solutions
• On a conjecture of Sokal concerning roots of the independence polynomial
• Relative Distance--An Error Measure in Round-Off Error Analysis
• The complexity of approximating complex-valued Ising and Tutte partition functions
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• The roots of the independence polynomial of a clawfree graph

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)