Inapproximability of the independent set polynomial in the complex plane

We study the complexity of approximating the independent set polynomial $Z_G(\lambda )$ of a graph $G$ with maximum degree $\mathrm{\Delta }$ when the activity $\lambda$ is a complex number. This problem is already well understood when $\lambda$ is real using connections to the $\mathrm{\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 $\mathrm{\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 $\mathrm{\Delta }$-regular tree converges. These values carve a cardioid-shaped region ${\mathrm{\Lambda }}_{\mathrm{\Delta }}$ in the complex plane. Motivated by the picture in the real case, they asked whether ${\mathrm{\Lambda }}_{\mathrm{\Delta }}$ marks the true approximability threshold for general complex values $\lambda$. Our main result shows that for every $\lambda$ outside of ${\mathrm{\Lambda }}_{\mathrm{\Delta }}$, the problem of approximating $Z_G(\lambda )$ on graphs $G$ with maximum degree at most $\mathrm{\Delta }$ is indeed NP-hard. In fact, when $\lambda$ is outside of ${\mathrm{\Lambda }}_{\mathrm{\Delta }}$ 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 ${\mathrm{\Lambda }}_{\mathrm{\Delta }}$, 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.