2026-07-24T10:08:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20178 2024-07-02T07:52:49Z ddc:004 open_access

A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs Carlson, Charlie Davies, Ewan Kolla, Alexandra Potukuchi, Aditya approximate counting independent sets bipartite graphs graph containers 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. Our contributions include a novel extension of the method of graph containers that differs considerably from other recent low-temperature algorithms. The additional key insights come from spectral graph theory and have previously been successful in approximation algorithms. As a result, we can overcome some limitations that seem inherent to the aforementioned class of algorithms. In particular, we exploit 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Charlie Carlson and Ewan Davies and Alexandra Kolla and Aditya Potukuchi 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.35 urn:nbn:de:0030-drops-201782 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode