Galanis, Andreas ;
Goldberg, Leslie Ann ;
Stefankovic, Daniel
Inapproximability of the Independent Set Polynomial Below the Shearer Threshold
Abstract
We study the problem of approximately evaluating the independent set polynomial of boundeddegree graphs at a point lambda or, equivalently, the problem of approximating the partition function of the hardcore 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)=(D1)^(D1)/(D2)^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)=(D1)^(D1)/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 NPhard 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 NPhard.
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).
BibTeX  Entry
@InProceedings{galanis_et_al:LIPIcs:2017:7396,
author = {Andreas Galanis and Leslie Ann Goldberg and Daniel Stefankovic},
title = {{Inapproximability of the Independent Set Polynomial Below the Shearer Threshold}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {28:128:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7396},
URN = {urn:nbn:de:0030drops73962},
doi = {10.4230/LIPIcs.ICALP.2017.28},
annote = {Keywords: approximate counting, independent set polynomial, Shearer threshold}
}
07.07.2017
Keywords: 

approximate counting, independent set polynomial, Shearer threshold 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 