Computing the partition function for cliques in a graph
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Abstract: We present a deterministic algorithm which, given a graph G with n vertices and an integer 1<m < n, computes in n^{O(ln m)} time the sum of weights w(S) over all m-subsets S of the set of vertices of G, where w(S)=exp{gamma t m +O(1/m)} provided exactly t{m choose 2} pairs of vertices of S span an edge of G for some 0 < t < 1. Here gamma >0 is an absolute constant: we can choose gamma=0.06, and if n > 4m and m > 10, we can choose gamma=0.18. This allows us to tell apart the graphs that do not have m-subsets of high density from the graphs that have sufficiently many m-subsets of high density, even when the probability to hit such a subset at random is exponentially small in m.
Recommendations
- Testing for dense subsets in a graph via the partition function
- Approximately counting cliques
- Computing the partition function for graph homomorphisms with multiplicities
- Some algorithmic applications of partition functions in combinatorics
- Computing the partition function for perfect matchings in a hypergraph
Cited in
(19)- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- The Ising partition function: zeros and deterministic approximation
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Algorithmic Pirogov-Sinai theory
- On a conjecture of Sokal concerning roots of the independence polynomial
- Computing the permanent of (some) complex matrices
- Approximately counting cliques
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Computing the partition function of a polynomial on the Boolean cube
- Approximating permanents and hafnians
- Testing for dense subsets in a graph via the partition function
- Gauges, loops, and polynomials for partition functions of graphical models
- Correlation decay and the absence of zeros property of partition functions
- Spectral independence via stability and applications to Holant-type problems
- Computing the partition function for graph homomorphisms
- Perfect sampling of \(q\)-spin systems on \(\mathbb{Z}^2\) via weak spatial mixing
- On the evolution of structure in triangle-free graphs
- On Dedekind's problem, a sparse version of Sperner's theorem, and antichains of a given size in the Boolean lattice
- Computing the partition function for graph homomorphisms with multiplicities
This page was built for publication: Computing the partition function for cliques in a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3467519)
