Approximately counting independent sets in bipartite graphs via graph containers

DOI10.1002/RSA.21145MaRDI QIDQ6074723zbMATH OpenFDO

Authors Matthew Jenssen, Will Perkins, Aditya Potukuchi

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.03744, https://birmingham.elsevierpure.com/en/publications/a066e358-e691-4d81-a0d2-570085f08242

zbMATH Keywords

\#BISapproximate countinggraph containersindependent sets

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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$-regular, bipartite graphs satisfying a weak expansion condition: when $d$ is constant, and the graph is a bipartite $Omega(lo{g}^{2}d/d)$-expander, we obtain an FPTAS for the number of independent sets. Previously such a result for $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$-regular, bipartite $alpha$-expander, with $alpha>0$ fixed, we give an FPTAS for the hard-core model partition function at fugacity $lambda=Omega(logd/d^{1/4})$. Finally we present an algorithm that applies to all $d$-regular, bipartite graphs, runs in time $expleft(Oleft(ncdotfraclo{g}^{3}ddight)ight)$, and outputs a $(1+o(1))$-approximation to the number of independent sets.

Recommendations

• Faster exponential-time algorithms for approximately counting independent sets
• Algorithms for \#BIS-hard problems on expander graphs
• Algorithms for #BIS-hard problems on expander graphs
• FPTAS for \#BIS with degree bounds on one side
• Counting independent sets in graphs with bounded bipartite pathwidth

Cites work

• A proof of the upper matching conjecture for large graphs
• A threshold phenomenon for random independent sets in the discrete hypercube
• Algorithmic Pirogov-Sinai theory
• Algorithms for \#BIS-hard problems on expander graphs
• Cluster expansion for abstract polymer models
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Counting independent sets in graphs
• Counting independent sets in unbalanced bipartite graphs
• Counting independent sets up to the tree threshold
• Counting maximal antichains and independent sets
• Eigenvalue bounds for independent sets
• Fast algorithms at low temperatures via Markov chains†
• Fast algorithms for general spin systems on bipartite expanders
• Fast mixing via polymers for random graphs with unbounded degree
• Faster exponential-time algorithms for approximately counting independent sets
• Faster graph coloring in polynomial space
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• FPTAS for \#BIS with degree bounds on one side
• Hoffman's ratio bound
• How to Play Unique Games on Expanders
• scientific article; zbMATH DE number 3833857 (Why is no real title available?)
• scientific article; zbMATH DE number 4160792 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Independent sets in the hypercube revisited
• Independent sets in the middle two layers of Boolean lattice
• Independent sets of a given size and structure in the hypercube
• On the number of graphs without 4-cycles
• On the ratio of optimal integral and fractional covers
• On the Shannon capacity of a graph
• Partitioning into expanders
• Sampling 3-colourings of regular bipartite graphs
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• Spectral algorithms for unique games
• Subexponential algorithms for unique games and related problems
• The Asymptotic Number of Lattices
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Ferromagnetic Ising with Local Fields
• The number of independent sets in graphs
• The relative complexity of approximate counting problems
• Torpid mixing of local Markov chains on 3-colorings of the discrete torus
• Two combinatorial covering theorems
• Unique games on expanding constraint graphs are easy (extended abstract)

Cited in

(12)

• Counting independent sets in graphs with bounded bipartite pathwidth
• Algorithms for \#BIS-hard problems on expander graphs
• Efficient algorithms for the Potts model on small-set expanders
• Lipschitz functions on weak expanders
• Counting independent sets in percolated graphs via the Ising model
• A refined graph container lemma and applications to the hard-core model on bipartite expanders
• A spectral approach to approximately counting independent sets in dense bipartite graphs
• Testing graph properties with the container method
• Independent sets in discrete tori of odd sidelength
• Low-temperature sampling on sparse random graphs
• Rapid mixing via coupling independence for spin systems with unbounded degree
• Low-temperature sampling on sparse random graphs

This page was built for publication: Approximately counting independent sets in bipartite graphs via graph containers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074723)