Approximately counting independent sets in bipartite graphs via graph containers
Approximately counting independent sets in bipartite graphs via graph containers
复制标题
通过图容器近似计算二分图中的独立集
DOI：
10.1137/1.9781611977073.24
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Potukuchi, Aditya
中科院分区：
文献类型：
--
作者：
Jenssen, Matthew;Perkins, Will;Potukuchi, Aditya
通过实现Sapozhenko图容器方法的算法版本，我们给出了逼近二部图中独立集数目的新算法。我们的第一个算法适用于d $$ d $$‐满足弱展开条件的正则二部图：当d $$ d $$是常数，并且图是二部Ω（log2d/d） $$ \Omega \left({\log}^2d/d\right) $$‐展开器时，我们获得独立集数量的FPTAS。在此之前，对于d bbb50 $$ d>5 $$这样的结果只在满足随机二部图的更强的展开条件的图中才知道。该算法也适用于加权独立集：对于d $$ d $$‐正则，二部α $$ \alpha $$‐扩展器，α>0 $$ \alpha >0 $$固定，我们给出了在逃逸率λ=Ω（logd/d1/4） $$ \lambda =\Omega \left(\log d/{d}^{1/4}\right) $$下的硬核模型配分函数的FPTAS。最后，我们提出了一种算法，该算法适用于所有d $$ d $$‐正则二部图，运行时间为expOn·log3dd $$ \exp \left(O\left(n\cdotp \frac{\log^3d}{d}\right)\right) $$，并输出（1+o(1)） $$ \left(1+o(1)\right) $$‐对独立集数量的近似。
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.
登录
查看更多内容
DOI：
10.1016/j.jctb.2021.07.005
发表时间：
2021
期刊：
Series B
影响因子：
--
作者：
Davies, Ewan;Jenssen, Matthew;Perkins, Will
通讯作者：
Perkins, Will
关于扩展器中独立组的数量
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
А.А. Сапоженко;A. A. Sapozhenko
通讯作者：
A. A. Sapozhenko
西奈半岛
DOI：
--
发表时间：
2021
期刊：
Encyclopedic Dictionary of Archaeology
影响因子：
--
作者：
Brigitte Wirtz;Christoph Maggioni
通讯作者：
Christoph Maggioni
独特游戏的谱算法
DOI：
--
发表时间：
2010
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
A. Kolla
通讯作者：
A. Kolla
多项式空间中更快的图形着色
影响因子：
1.1
作者：
Serge Gaspers;Edward J. Lee
通讯作者：
Edward J. Lee