Details

Autor(en) / Beteiligte

• Jenssen, Matthew
• Perkins, Will
• Potukuchi, Aditya

Titel

Approximately counting independent sets in bipartite graphs via graph containers

Ist Teil von

• Random structures & algorithms, 2023-08, Vol.63 (1), p.215-241

Ort / Verlag

New York: John Wiley & Sons, Inc

Erscheinungsjahr

2023

Quelle

Wiley-Blackwell Journals

Beschreibungen/Notizen

• 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$$ d $$‐regular, bipartite graphs satisfying a weak expansion condition: when d$$ d $$ is constant, and the graph is a bipartite Ω(log2d/d)$$ \Omega \left({\log}^2d/d\right) $$‐expander, we obtain an FPTAS for the number of independent sets. Previously such a result for d>5$$ 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$$ d $$‐regular, bipartite α$$ \alpha $$‐expander, with α>0$$ \alpha >0 $$ fixed, we give an FPTAS for the hard‐core model partition function at fugacity λ=Ω(logd/d1/4)$$ \lambda =\Omega \left(\log d/{d}^{1/4}\right) $$. Finally we present an algorithm that applies to all d$$ d $$‐regular, bipartite graphs, runs in time expOn·log3dd$$ \exp \left(O\left(n\cdotp \frac{\log^3d}{d}\right)\right) $$, and outputs a (1+o(1))$$ \left(1+o(1)\right) $$‐approximation to the number of independent sets.