License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.28
URN: urn:nbn:de:0030-drops-73962
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7396/
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 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).
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:1--28:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7396},
URN = {urn:nbn:de:0030-drops-73962},
doi = {10.4230/LIPIcs.ICALP.2017.28},
annote = {Keywords: approximate counting, independent set polynomial, Shearer threshold}
}
|
Keywords: |
|
approximate counting, independent set polynomial, Shearer threshold |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
