论文标题
更快的指数时间算法用于大约计数独立集
Faster Exponential-time Algorithms for Approximately Counting Independent Sets
论文作者
论文摘要
计算图的独立集是一个经典的＃P-Complete问题，即使在两部分情况下也是如此。我们为此问题提供了一个指数时间近似方案，该方案比确切问题的最著名算法要快。我们在具有错误公差$ \ varepsilon $的一般图表上的算法运行时间最多是$ o（2^{0.2680N}）$ times a polyenmial in $ 1/\ varepsilon $。在双分图上，运行时间中的指数项提高到$ O（2^{0.2372N}）$。我们的方法将精确指数算法的技术与近似计数的技术结合在一起。在此过程中，我们将Sinclair，Srivastava，Štefankovič和Yin的FPTA（多元案例）推广，以近似具有有界连接常数的图形上的硬核分区函数。同样，我们获得了一个FPTA，用于在图形上计数独立集，而没有至少6度的顶点，其邻居的学位总和为27或更多。由于SLY的结果，除非$ \ mbox {p} = \ mbox {np} $，否则没有最高度6的图形。
Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is faster than the best known algorithm for the exact problem. The running time of our algorithm on general graphs with error tolerance $\varepsilon$ is at most $O(2^{0.2680n})$ times a polynomial in $1/\varepsilon$. On bipartite graphs, the exponential term in the running time is improved to $O(2^{0.2372n})$. Our methods combine techniques from exact exponential algorithms with techniques from approximate counting. Along the way we generalise (to the multivariate case) the FPTAS of Sinclair, Srivastava, Štefankovič and Yin for approximating the hard-core partition function on graphs with bounded connective constant. Also, we obtain an FPTAS for counting independent sets on graphs with no vertices with degree at least 6 whose neighbours' degrees sum to 27 or more. By a result of Sly, there is no FPTAS that applies to all graphs with maximum degree 6 unless $\mbox{P}=\mbox{NP}$.
