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
AUTHORS (3)
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 ....