Approximately counting independent sets in bipartite graphs via graph containers

• DOI: 10.1002/rsa.21145
• Publication Date: 2023-02-15T12:21:16Z
• Authors: Matthew Jenssen; Will Perkins; Aditya Potukuchi
• Keywords: Complete bipartite graph; Cograph; Maximal independent set

Abstract By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number independent sets in bipartite graphs. Our first algorithm applies to ‐regular, graphs satisfying a weak expansion condition: when is constant, and ‐expander, obtain an FPTAS sets. Previously such result was known only much stronger conditions random The also weighted sets: with fixed, hard‐core model partition function at fugacity . Finally present that all graphs, runs time , outputs ‐approximation