FPTAS for #BIS with Degree Bounds on One Side

DOI10.1145/2746539.2746598zbMath1321.05185arXiv1412.0073OpenAlexW2068344352MaRDI QIDQ2941547

Pinyan Lu, Jing-Cheng Liu

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

independent setsFPTASapproximate countingcorrelation decay\#BIS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Algorithmic Pirogov-Sinai theory ⋮ Fast algorithms at low temperatures via Markov chains† ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ A fixed-parameter perspective on \#BIS ⋮ On a conjecture of Sokal concerning roots of the independence polynomial ⋮ Unnamed Item ⋮ Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming