Computing the partition function for graph homomorphisms
From MaRDI portal
Abstract: We introduce the partition function of edge-colored graph homomorphisms, of which the usual partition function of graph homomorphisms is a specialization, and present an efficient algorithm to approximate it in a certain domain. Corollaries include efficient algorithms for computing weighted sums approximating the number of k-colorings and the number of independent sets in a graph, as well as an efficient procedure to distinguish pairs of edge-colored graphs with many color-preserving homomorphisms G --> H from pairs of graphs that need to be substantially modified to acquire a color-preserving homomorphism G --> H.
Recommendations
- Computing the partition function for graph homomorphisms with multiplicities
- A computational framework for the study of partition functions and graph polynomials
- Computing the partition function for cliques in a graph
- Computing the partition function for perfect matchings in a hypergraph
- A complexity dichotomy for hypergraph partition functions
- scientific article; zbMATH DE number 1545676
- Complexity of graph partition problems
- scientific article; zbMATH DE number 434481
- Domatic partitions of computable graphs
- Counting graph homomorphisms
Cites work
- Approximate graph coloring by semidefinite programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Coloring -colorable graphs using relatively small palettes
- Computing the partition function for cliques in a graph
- Computing the permanent of (some) complex matrices
- Counting independent sets up to the tree threshold
- Graph homomorphisms with complex values: a dichotomy theorem
- Homomorphisms of edge-colored graphs and Coxeter groups
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Large networks and graph limits
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
- Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
- The complexity of partition functions
- Zero knowledge and the chromatic number
Cited in
(17)- On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
- Computing the partition function for graph homomorphisms with multiplicities
- Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
- The Ising partition function: zeros and deterministic approximation
- Computing the permanent of (some) complex matrices
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Spectral independence via stability and applications to Holant-type problems
- Absence of zeros implies strong spatial mixing
- On a conjecture of Sokal concerning roots of the independence polynomial
- Edge-reflection positivity and weighted graph homomorphisms
- On the zeroes of hypergraph independence polynomials
- A short proof of the equivalence of left and right convergence for sparse graphs
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Exact and approximate compression of transfer matrices for graph homomorphisms
- Fisher zeros and correlation decay in the Ising model
- Fisher Zeros and Correlation Decay in the Ising Model
This page was built for publication: Computing the partition function for graph homomorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q681595)
