Approximately counting independent sets in bipartite graphs via graph containers

Complete bipartite graph Cograph Maximal independent set
DOI: 10.1002/rsa.21145 Publication Date: 2023-02-15T12:21:16Z
ABSTRACT
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
SUPPLEMENTAL MATERIAL
Coming soon ....
REFERENCES (55)
CITATIONS (3)
EXTERNAL LINKS
PlumX Metrics
RECOMMENDATIONS
FAIR ASSESSMENT
Coming soon ....
JUPYTER LAB
Coming soon ....