Title: Inapproximability of the independent set polynomial in the complex plane,
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 $\Lambda_\Delta$ in the complex plane. 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. If $\lambda$ is a
negative real number outside of $\Lambda_\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.