Counting Independent Sets in Unbalanced Bipartite Graphs
Counting Independent Sets in Unbalanced Bipartite Graphs
复制标题
计算不平衡二分图中的独立集
DOI：
10.1137/1.9781611975994.88
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Perkins, Will
中科院分区：
文献类型：
--
作者：
Cannon, Sarah;Perkins, Will
了解近似计算二分图（#BIS）中加权或未加权独立集数量的复杂性是近似计数领域的一个核心开放问题。在这里，我们考虑这个问题的一个子类，并给出一个 FPTAS，当二分图的边（L，R）之间的度或逸度存在足够的不平衡时，用于逼近二分图的硬核模型的配分函数。其中包括当 λ = 1（近似独立 G 组的数量）和 ΔR≥ 7ΔLlog(ΔL) 时的双正则情况。我们的近似算法基于截断聚合物模型配分函数的簇展开，该函数根据与二分一侧为空的独立集的偏差来表达硬核配分函数。该方法对不平衡二分图的进一步影响包括硬核模型的有效采样算法和具有复杂逸度的配分函数的零自由度结果。通过利用簇扩展和某些随机变量的联合累积量之间的联系，我们超越了簇扩展的先前算法应用，证明了硬核模型对于满足我们的条件的所有图和逸度表现出相关性的指数衰减。这说明了统计力学工具对算法问题的适用性，并加深了我们对不同近似计数方法之间联系的理解。
Understanding the complexity of approximately counting the number of weighted or unweighted independent sets in a bipartite graph (#BIS) is a central open problem in the field of approximate counting. Here we consider a subclass of this problem and give an FPTAS for approximating the partition function of the hard-core model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the sides (L, R) of the bipartition. This includes, among others, the biregular case when λ = 1 (approximating the number of independent sets ofG) and ΔR≥ 7ΔLlog(ΔL). Our approximation algorithm is based on truncating the cluster expansion of a polymer model partition function that expresses the hard-core partition function in terms of deviations from independent sets that are empty on one side of the bipartition.Further consequences of this method for unbalanced bipartite graphs include an efficient sampling algorithm for the hard-core model and zero-freeness results for the partition function with complex fugacities. By utilizing connections between the cluster expansion and joint cumulants of certain random variables, we go beyond previous algorithmic applications of the cluster expansion to prove that the hard-core model exhibits exponential decay of correlations for all graphs and fugacities satisfying our conditions. This illustrates the applicability of statistical mechanics tools to algorithmic problems and refines our understanding of the connections between different methods of approximate counting.