Testing for Dense Subsets in a Graph via the Partition Function

DOI10.1137/19M1247413zbMath1431.05119arXiv1807.02054OpenAlexW3003340671MaRDI QIDQ5212953

Anthony della Pella, Alexander I. Barvinok

Publication date: 31 January 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmpartition functiondensitycomplex zeros

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorics and complexity of partition functions
• Quick approximation to matrices and applications
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Detecting high log-densities
• Computing the partition function for cliques in a graph
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Introduction to Property Testing