Inapproximability of the independent set polynomial in the complex plane

DOI10.1145/3188745.3188788MaRDI QIDQ5230376zbMATH OpenOpenAlexFDO

Authors Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, D. Štefankovič

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

\(\#\)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)

Abstract: We study the complexity of approximating the independent set polynomial $Z_G(lambda)$ of a graph $G$ with maximum degree $Delta$ when the activity $lambda$ is a complex number. This problem is already well understood when $lambda$ is real using connections to the $Delta$-regular tree $T$. The key concept in that case is the "occupation ratio" of the tree $T$. This ratio is the contribution to $Z_T(lambda)$ from independent sets containing the root of the tree, divided by $Z_T(lambda)$ itself. If $lambda$ is such that the occupation ratio converges to a limit, as the height of $T$ grows, then there is an FPTAS for approximating $Z_G(lambda)$ on a graph $G$ with maximum degree $Delta$. Otherwise, the approximation problem is NP-hard. Unsurprisingly, the case where $lambda$ is complex is more challenging. Peters and Regts identified the complex values of $lambda$ for which the occupation ratio of the $Delta$-regular tree converges. These values carve a cardioid-shaped region $Lambd{a}_{D}elta$ in the complex plane. Motivated by the picture in the real case, they asked whether $Lambd{a}_{D}elta$ marks the true approximability threshold for general complex values $lambda$. Our main result shows that for every $lambda$ outside of $Lambd{a}_{D}elta$, the problem of approximating $Z_G(lambda)$ on graphs $G$ with maximum degree at most $Delta$ is indeed NP-hard. In fact, when $lambda$ is outside of $Lambd{a}_{D}elta$ and is not a positive real number, we give the stronger result that approximating $Z_G(lambda)$ is actually #P-hard. If $lambda$ is a negative real number outside of $Lambd{a}_{D}elta$, we show that it is #P-hard to even decide whether $Z_G(lambda)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava and Vondrak. Our proof techniques are based around tools from complex analysis - specifically the study of iterative multivariate rational maps.

Recommendations

• Inapproximability of the independent set polynomial in the complex plane
• scientific article; zbMATH DE number 7204480
• scientific article; zbMATH DE number 4040472
• Inapproximability of the Tutte polynomial
• Inapproximability of the Tutte polynomial
• The degree of approximation by polynomials on some disjoint intervals in the complex plane
• scientific article; zbMATH DE number 1191145
• scientific article; zbMATH DE number 4010508
• The complexity of approximating the matching polynomial in the complex plane
• The Complexity of Approximating the Matching Polynomial in the Complex Plane

Cited in

(16)

• Implementations and the independent set polynomial below the Shearer threshold
• Algorithmic Pirogov-Sinai theory
• Cayley trees do not determine the maximal zero-free locus of the independence polynomial
• On a conjecture of Sokal concerning roots of the independence polynomial
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Polylogarithmic inapproximability
• Computing the independence polynomial: from the tree threshold down to the roots
• A spectral independence view on hard spheres via block dynamics
• The complexity of approximating the complex-valued Potts model
• scientific article; zbMATH DE number 7559110 (Why is no real title available?)
• The complexity of approximating the matching polynomial in the complex plane
• scientific article; zbMATH DE number 7204480 (Why is no real title available?)
• Inapproximability of the independent set polynomial in the complex plane
• Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
• Counting independent sets in percolated graphs via the Ising model
• A spectral independence view on hard spheres via block dynamics

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 Q5230376)