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.APPROX-RANDOM.2016.46
URN: urn:nbn:de:0030-drops-66690
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6669/
Go to the corresponding LIPIcs Volume Portal

Song, Renjie ; Yin, Yitong ; Zhao, Jinman

Counting Hypergraph Matchings up to Uniqueness Threshold

pdf-format:
LIPIcs-APPROX-RANDOM-2016-46.pdf (2 MB)

Abstract

We study the problem of approximately counting matchings in hypergraphs of bounded maximum degree and maximum size of hyperedges. With an activity parameter lambda, each matching M is assigned a weight lambda^{|M|}. The counting problem is formulated as computing a partition function that gives the sum of the weights of all matchings in a hypergraph. This problem unifies two extensively studied statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer-dimer model (graph matchings).

For this model, the critical activity lambda_c= (d^d)/(k (d-1)^{d+1}) is the threshold for the uniqueness of Gibbs measures on the infinite (d+1)-uniform (k+1)-regular hypertree. Consider hypergraphs of maximum degree at most k+1 and maximum size of hyperedges at most d+1. We show that when lambda < lambda_c, there is an FPTAS for computing the partition function; and when lambda = lambda_c, there is a PTAS for computing the log-partition function. These algorithms are based on the decay of correlation (strong spatial mixing) property of Gibbs distributions. When lambda > 2lambda_c, there is no PRAS for the partition function or the log-partition function unless NP=RP.

Towards obtaining a sharp transition of computational complexity of approximate counting, we study the local convergence from a sequence of finite hypergraphs to the infinite lattice with specified symmetry. We show a surprising connection between the local convergence and the reversibility of a natural random walk. This leads us to a barrier for the hardness result: The non-uniqueness of infinite Gibbs measure is not realizable by any finite gadgets.

BibTeX - Entry

@InProceedings{song_et_al:LIPIcs:2016:6669,
  author =	{Renjie Song and Yitong Yin and Jinman Zhao},
  title =	{{Counting Hypergraph Matchings up to Uniqueness Threshold}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{46:1--46:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6669},
  URN =		{urn:nbn:de:0030-drops-66690},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.46},
  annote =	{Keywords: approximate counting; phase transition; spatial mixing}
}

Keywords: approximate counting; phase transition; spatial mixing
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI