Galanis, Andreas
[Verfasser:in];
Goldberg, Leslie Ann
[Verfasser:in];
Stefankovic, Daniel
[Verfasser:in]
;
Andreas Galanis and Leslie Ann Goldberg and Daniel Stefankovic
[Mitwirkende:r]
Inapproximability of the Independent Set Polynomial Below the Shearer Threshold
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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<0, the evaluation of the independent set polynomial is connected to the conditions of the Lovasz Local Lemma. Shearer identified the threshold lambda*(D)=(D-1)^(D-1)/D^D as the maximum value p such that every family of events with failure probability at most p and whose dependency graph has max degree D has nonempty intersection. Very recently, Patel and Regts, and Harvey et al. have independently designed FPTASes for approximating the partition function whenever |lambda|<lambda*(D). Our main result establishes for the first time a computational transition at the Shearer threshold. We show that for all D>=3, for all lambda<-lambda*(D), it is NP-hard to approximate the partition function on graphs of maximum degree D, even within an exponential factor. Thus, our result, combined with the FPTASes for 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<lambda_c(D), the problem admits an FPTAS. 2. For lambda<-lambda*(D) or lambda>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).