Inapproximability of the independent set polynomial in the complex plane
Inapproximability of the independent set polynomial in the complex plane
复制标题
复平面上独立集合多项式的不可逼近性
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Daniel Stefankovic
中科院分区：
文献类型：
--
作者：
Ivona Bezáková;Andreas Galanis;L. A. Goldberg;Daniel Stefankovic
研究了当活度λ为复数时，最大度为Δ的图G的独立集多项式ZG（λ）的逼近复杂度。当λ为实数时，复杂性图被很好地理解，并由两个实值阈值λ*和λc捕获，它们依赖于Δ并且满足0<λ*<λc。已知如果λ是区间（−λ*,λc）内的实数，则在图G上存在一个最大度不超过Δ的近似ZG（λ）的FPTAS。另一方面，如果λ是（闭）区间外的实数，则近似是np困难的。建立这幅图的关键是对Δ-regular树上的阈值λ*和λc的解释。Δ-regular树T的“占用率”是包含树的根的独立集合对ZT（λ）的贡献，除以ZT（λ）本身。当且仅当λ∈[−λ*，λc]时，随着树的高度的增长，该占用率收敛于一个极限。不出所料，λ是复数的情况更具挑战性。已知当λ是范数最多为λ*的复数时，以及λ在实区间[0，λc)周围的小条内时，存在一个FPTAS。然而，这两种结果都不能完全说明什么时候近似是可能的。Peters和Regts确定了λ的值，其中Δ-regular树的占用率收敛。这些值在复平面上雕刻出一个心形区域ΛΔ，其边界包括临界点- λ*和λc。在真实情况下的图片的激励下，他们问ΛΔ是否标志着一般复数值λ的真实近似阈值。我们的主要结果表明，对于ΛΔ以外的每个λ，在图G上以最大度（最多Δ）逼近ZG（λ）的问题确实是np困难的。事实上，当λ在ΛΔ之外并且不是正实数时，我们给出了更强的结果，即近似ZG（λ）实际上是#P-hard。进一步，在负实轴上，当λ<−λ*时，我们证明了ZG(λ)>是否为#P-hard，从而肯定了Harvey， Srivastava和Vondrak的一个猜想。我们的证明技术是基于复杂分析的工具-特别是迭代多元理性映射的研究。
We study the complexity of approximating the value of the independent set polynomial ZG(λ) of a graph G with maximum degree Δ when the activity λ is a complex number. When λ is real, the complexity picture is well-understood, and is captured by two real-valued thresholds λ* and λc, which depend on Δ and satisfy 0<λ*<λc. It is known that if λ is a real number in the interval (−λ*,λc) then there is an FPTAS for approximating ZG(λ) on graphs G with maximum degree at most Δ. On the other hand, if λ 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 λ* and λc on the Δ-regular tree. The ”occupation ratio” of a Δ-regular tree T is the contribution to ZT(λ) from independent sets containing the root of the tree, divided by ZT(λ) itself. This occupation ratio converges to a limit, as the height of the tree grows, if and only if λ∈ [−λ*,λc]. Unsurprisingly, the case where λ is complex is more challenging. It is known that there is an FPTAS when λ is a complex number with norm at most λ* and also when λ is in a small strip surrounding the real interval [0,λc). However, neither of these results is believed to fully capture the truth about when approximation is possible. Peters and Regts identified the values of λ for which the occupation ratio of the Δ-regular tree converges. These values carve a cardioid-shaped region ΛΔ in the complex plane, whose boundary includes the critical points −λ* and λc. 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. Further, on the negative real axis, when λ<−λ*, 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.