Abstract
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of anti-ferromagnetic two-spin models.
Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. In this paper, we develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and we amortise against certain bad instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an FPTAS even when strong spatial mixing fails.
We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper-bound Δ and with a lower bound k on the arity of hyperedges. Liu and Lin gave an FPTAS for k ≥ 2 and Δ ≤ 5 (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalised to Δ = 6). Our technique gives a tight result for Δ = 6, showing that there is an FPTAS for k ≥ 3 and Δ ≤ 6. The best previously-known approximation scheme for Δ = 6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer and Karpinski, which only works for k ≥ 8.
Our technique also applies for larger values of k, giving an FPTAS for k ≥ Δ. This bound is not substantially stronger than existing randomised results in the literature. Nevertheless, it gives the first deterministic approximation scheme in this regime. Moreover, unlike existing results, it leads to an FPTAS for counting dominating sets in regular graphs with sufficiently large degree.We further demonstrate that in the hypergraph independent set model, approximating
the partition function is NP-hard even within the uniqueness regime. Also, approximately counting dominating sets of bounded-degree graphs (without the regularity restriction) is NP-hard.
Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. In this paper, we develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and we amortise against certain bad instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an FPTAS even when strong spatial mixing fails.
We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper-bound Δ and with a lower bound k on the arity of hyperedges. Liu and Lin gave an FPTAS for k ≥ 2 and Δ ≤ 5 (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalised to Δ = 6). Our technique gives a tight result for Δ = 6, showing that there is an FPTAS for k ≥ 3 and Δ ≤ 6. The best previously-known approximation scheme for Δ = 6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer and Karpinski, which only works for k ≥ 8.
Our technique also applies for larger values of k, giving an FPTAS for k ≥ Δ. This bound is not substantially stronger than existing randomised results in the literature. Nevertheless, it gives the first deterministic approximation scheme in this regime. Moreover, unlike existing results, it leads to an FPTAS for counting dominating sets in regular graphs with sufficiently large degree.We further demonstrate that in the hypergraph independent set model, approximating
the partition function is NP-hard even within the uniqueness regime. Also, approximately counting dominating sets of bounded-degree graphs (without the regularity restriction) is NP-hard.
Original language | English |
---|---|
Title of host publication | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy |
Editors | Ioannis Chatzigiannakis |
Place of Publication | Rome, Italy |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany |
Pages | 45:1-45:13 |
Number of pages | 13 |
Volume | 55 |
ISBN (Print) | 978-3-95977-013-2 |
DOIs | |
Publication status | Published - 15 Jul 2016 |
Event | 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science - Sapienza University of Rome, Rome, Italy Duration: 12 Jul 2016 → 15 Jul 2016 http://www.easyconferences.eu/icalp2016/ http://www.easyconferences.eu/icalp2016/index.html |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 55 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science |
---|---|
Abbreviated title | ICALP 2016 |
Country/Territory | Italy |
City | Rome |
Period | 12/07/16 → 15/07/16 |
Internet address |