Approximately counting independent sets in bipartite graphs via graph containers

2021/09/08 by Jenssen, Matthew, Perkins, Will, Potukuchi, Aditya · 2 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2109.03744

Abstract

By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. Our first algorithm applies to d-regular, bipartite graphs satisfying a weak expansion condition: when d is constant, and the graph is a bipartite Ω( log² d/d)-expander, we obtain an FPTAS for the number of independent sets. Previously such a result for d>5 was known only for graphs satisfying the much stronger expansion conditions of random bipartite graphs. The algorithm also applies to weighted independent sets: for a d-regular, bipartite α-expander, with α>0 fixed, we give an FPTAS for the hard-core model partition function at fugacity λ=Ω(log d / d^1/4). Finally we present an algorithm that applies to all d-regular, bipartite graphs, runs in time exp( O( n ⋅ ( log³ d )/(d ) ) ), and outputs a (1 + o(1))-approximation to the number of independent sets.

Cited by

• Aggregating maximal cliques in real-world graphs
• Asymptotic enumeration via graph containers and entropy

Related

• Counting independent sets in unbalanced bipartite graphs
• Counting independent sets in expanding bipartite regular graphs
• Faster Exponential-time Algorithms for Approximately Counting Independent Sets
• Approximately counting independent sets in dense bipartite graphs via subspace enumeration
• Counting independent sets and colorings on random regular bipartite graphs