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

\#P-hardnessinapproximabilityindependent set polynomial

Mathematics Subject Classification ID

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

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

• 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)
• 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?)
• 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

(17)

• Implementations and the independent set polynomial below the Shearer threshold
• The complexity of approximating the complex-valued Potts model
• Polylogarithmic inapproximability
• Computing the independence polynomial: from the tree threshold down to the roots
• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• The complexity of approximating the matching polynomial in the complex plane
• Inapproximability of the independent set polynomial in the complex plane
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• 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
• On the zeroes of hypergraph independence polynomials
• Zero-free regions for the independence polynomial on restricted graph classes
• Two-state spin systems with negative interactions
• Two-state spin systems with negative interactions
• The limit of the zero locus of the independence polynomial for bounded degree graphs

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)