Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

Publication date: 28 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.04984

zbMATH Keywords

sampling independent sets approximate counting hard-core model FPRAS computational threshold

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

Unnamed Item
Unnamed Item
Central limit theorems, Lee-Yang zeros, and graph-counting polynomials
Decay of correlations for the hardcore model on the $d$-regular random graph
Counting in two-spin models on $d$-regular graphs
Combinatorics and complexity of partition functions
Gibbs measures and phase transitions.
On the complexity of fixed parameter clique and dominating set
Approximate counting, uniform generation and rapidly mixing Markov chains
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
The relative complexity of approximate counting problems
A proof of the upper matching conjecture for large graphs
A fixed-parameter perspective on \#BIS
On a conjecture of Sokal concerning roots of the independence polynomial
Central limit theorems from the roots of probability generating functions
The maximum number of complete subgraphs in a graph with given maximum degree
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Counting independent sets up to the tree threshold
Polynomial-Time Approximation Algorithms for the Ising Model
Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
Approximating the Permanent
The Complexity of Enumeration and Reliability Problems
Extremal Regular Graphs: Independent Sets and Graph Homomorphisms
On the average size of independent sets in triangle-free graphs
Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
On Approximating the Number of $k$-Cliques in Sublinear Time
Improved analysis of higher order random walks and applications
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
Correlation Decay up to Uniqueness in Spin Systems
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Tight bounds on the coefficients of partition functions via stability
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion

This page was built for publication: Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs