Inapproximability of the independent set polynomial in the complex plane

Journal article

We study the complexity of approximating the value of the independent set polynomial $Z_G(\lambda)$ of a graph $G$ with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. When $\lambda$ is real, the complexity picture is well understood, and is captured by two real-valued thresholds $\lambda^*$ and $\lambda_c$, which depend on $\Delta$ and satisfy $0<\lambda^*<\lambda_c$. It is known that if $\lambda$ is a real number in the interval $(-\lambda^*,\lambda_c)$ then there is a fully polynomial time approximation scheme (FPTAS) for approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$. On the other hand, if $\lambda$ is a real number outside of the (closed) interval, then approximation is NP-hard. The key to establishing this picture was the interpretation of the thresholds $\lambda^*$ and $\lambda_c$ on the $\Delta$-regular tree. The “occupation ratio” of a $\Delta$-regular tree $T$ is the contribution to $Z_T(\lambda)$ from independent sets containing the root of the tree, divided by $Z_T(\lambda)$ itself. This occupation ratio converges to a limit, as the height of the tree grows, if and only if $\lambda\in [-\lambda^*,\lambda_c]$. Unsurprisingly, the case where $\lambda$ is complex is more challenging. It is known that there is an FPTAS when $\lambda$ is a complex number with norm at most $\lambda^*$ and also when $\lambda$ is in a small strip surrounding the real interval $[0,\lambda_c)$. However, neither of these results is believed to fully capture the truth about when approximation is possible. 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 $\Lambda_\Delta$ in the complex plane, whose boundary includes the critical points $-\lambda^*$ and $\lambda_c$. Motivated by the picture in the real case, they asked whether $\Lambda_\Delta$ marks the true approximability threshold for general complex values $\lambda$. Our main result shows that for every $\lambda$ outside of $\Lambda_\Delta$, 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 $\Lambda_\Delta$ and is not a positive real number, we give the stronger result that approximating $Z_G(\lambda)$ is actually \#P-hard. Further, on the negative real axis, when $\lambda < - \lambda^*$, 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 Vondrák. Our proof techniques are based around tools from complex analysis---specifically the study of iterative multivariate rational maps.

Authors: Bezáková, I; Galanis, A; Goldberg, LA; Štefankovič, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Computing
• Volume: 49
• Issue: 5
• Pages: STOC18-395-STOC18-448
• Publication date: 2020-09-24
• Acceptance date: 2020-06-29
• DOI: 10.1137/18M1184485
• EISSN: 1095-7111
• ISSN: 0097-5397
• Language: English
• Keywords: independent set polynomial,; inapproximability; FFR; \#P-hardness