Counting independent sets and colorings on random regular bipartite graphs

2019/03/18 by Liao, Chao, Lin, Jiabao, Lu, Pinyan +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1903.07531

Abstract

We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every Δ-regular bipartite graph if Δ≥ 53. In the weighted case, for all sufficiently large integers Δ and weight parameters λ=Ω(\frac1Δ), we also obtain an FPTAS on almost every Δ-regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all q≥ 3 and sufficiently large integers Δ=Δ(q), there is an FPTAS to count the number of q-colorings on almost every Δ-regular bipartite graph.

Related

• Approximately counting independent sets in bipartite graphs via graph containers
• Faster Exponential-time Algorithms for Approximately Counting Independent Sets
• Counting independent sets in expanding bipartite regular graphs
• Approximately counting independent sets in dense bipartite graphs via subspace enumeration
• Counting without sampling. New algorithms for enumeration problems using statistical physics