文章基本信息

标题：Inapproximability of the Independent Set Polynomial Below the Shearer Threshold
本地全文：下载
作者：Andreas Galanis ; Leslie Ann Goldberg ; Daniel Stefankovic 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：28:1-28:13
DOI：10.4230/LIPIcs.ICALP.2017.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the problem of approximately evaluating the independent set polynomial of bounded-degree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hard-core model with activity lambda on graphs G of max degree D. For lambda>0, breakthrough results of Weitz and Sly established a computational transition from easy to hard at lambda_c(D)=(D-1)^(D-1)/(D-2)^D, which coincides with the tree uniqueness phase transition from statistical physics. For lambda =3, for all lambda -lambda*(D), establishes a phase transition for negative activities. In fact, we now have the following picture for the problem of approximating the partition function with activity lambda on graphs G of max degree D. 1. For -lambda*(D) lambda_c(D), the problem is NP-hard. Rather than the tree uniqueness threshold of the positive case, the phase transition for negative activities corresponds to the existence of zeros for the partition function of the tree below -lambda*(D).
关键词：approximate counting; independent set polynomial; Shearer threshold