Approximately counting independent sets in dense bipartite graphs via subspace enumeration

07/18/2023
by   Charlie Carlson, et al.
0

We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph – in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to “high-temperature” problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. The proof exploits the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e. bounded threshold rank), which via subspace enumeration lets us enumerate small cuts efficiently.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset