Faster exponential-time algorithms for approximately counting independent sets

Journal article

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 ε is at most O(20.2680n) times a polynomial in 1/ε. On bipartite graphs, the exponential term in the running time is improved to O(20.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, Stefankoviˇc 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 P = NP.

Authors: Goldberg, L; Lapinskas, J; Richerby, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Volume: 892
• Pages: 48-84
• Publication date: 2021-09-16
• Acceptance date: 2021-09-02
• DOI: 10.1016/j.tcs.2021.09.009
• ISSN: 0304-3975
• Language: English
• Keywords: FFR; exponential algorithms; approximate counting; independent sets