Approximately counting independent sets in bipartite graphs via graph containers
FOS: Computer and information sciences
Computer Science - Data Structures and Algorithms
FOS: Mathematics
Mathematics - Combinatorics
Data Structures and Algorithms (cs.DS)
Combinatorics (math.CO)
0102 computer and information sciences
01 natural sciences
DOI:
10.1002/rsa.21145
Publication Date:
2023-02-15T12:21:16Z
AUTHORS (3)
ABSTRACT
AbstractBy 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 ‐regular, bipartite graphs satisfying a weak expansion condition: when is constant, and the graph is a bipartite ‐expander, we obtain an FPTAS for the number of independent sets. Previously such a result for 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 ‐regular, bipartite ‐expander, with fixed, we give an FPTAS for the hard‐core model partition function at fugacity . Finally we present an algorithm that applies to all ‐regular, bipartite graphs, runs in time , and outputs a ‐approximation to the number of independent sets.
SUPPLEMENTAL MATERIAL
Coming soon ....
REFERENCES (55)
CITATIONS (3)
EXTERNAL LINKS
PlumX Metrics
RECOMMENDATIONS
FAIR ASSESSMENT
Coming soon ....
JUPYTER LAB
Coming soon ....