Paper Info
Title
Inapproximability of the Independent Set Polynomial in the Complex Plane.
Abstract
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* 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 is an element of [-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 Vondrak. Our proof techniques are based around tools from complex analysis-specifically the study of iterative multivariate rational maps.
Year
DOI
Venue
2020
10.1137/18M1184485
SIAM JOURNAL ON COMPUTING
Keywords
DocType
Volume
independent set polynomial,inapproximability,#P-hardness
Journal
49
Issue
ISSN
Citations 
5
0097-5397
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Ivona Bezakova152.29
andreas galanis26815.13
leslie ann goldberg31411125.20
Daniel Stefankovic424328.65