Inapproximability of the independent set polynomial in the complex plane

Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +1

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 a…