2017/11/01 by Bezakova, Ivona, Galanis, Andreas, Goldberg, Leslie Ann +1 · 2 citations
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1711.00282
We study the complexity of approximating the independent set polynomial ZG(λ) of a graph G with maximum degree Δ when the activity λ is a complex number. This problem is already well understood when λ is real using connections to the Δ-regular tree T. The key concept in that case is the "occupation ratio" of the tree T. This ratio is the contribution to ZT(λ) from independent sets containing the root of the tree, divided by ZT(λ) itself. If λ is such that the occupation ratio converges to a limit, as the height of T grows, then there is an FPTAS for approximating ZG(λ) on a graph G with maximum degree Δ. Otherwise, the approximation problem is NP-hard. Unsurprisingly, the case where λ is complex is more challenging. Peters and Regts identified the complex values of λ for which the occupation ratio of the Δ-regular tree converges. These values carve a cardioid-shaped region ΛΔ in the complex plane. Motivated by the picture in the real case, they asked whether ΛΔ marks the true approximability threshold for general complex values λ. Our main result shows that for every λ outside of ΛΔ, the problem of approximating ZG(λ) on graphs G with maximum degree at most Δ is indeed NP-hard. In fact, when λ is outside of ΛΔ and is not a positive real number, we give the stronger result that approximating ZG(λ) is actually #P-hard. If λ is a negative real number outside of ΛΔ, we show that it is #P-hard to even decide whether ZG(λ)>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.