Computing the partition function for graph homomorphisms
From MaRDI portal
Publication:681595
DOI10.1007/S00493-016-3357-2zbMATH Open1399.05209arXiv1406.1771OpenAlexW2963793606MaRDI QIDQ681595FDOQ681595
Authors: Pablo Soberón, Alexander Barvinok 
Publication date: 12 February 2018
Published in: Combinatorica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1406.1771
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
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Approximation algorithms (68W25) Enumeration in graph theory (05C30)
Cites Work
- Large networks and graph limits
- Approximate graph coloring by semidefinite programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The complexity of partition functions
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Graph homomorphisms with complex values: a dichotomy theorem
- Counting independent sets up to the tree threshold
- 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
- Computing the permanent of (some) complex matrices
- Computing the partition function for cliques in a graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Zero knowledge and the chromatic number
- Homomorphisms of edge-colored graphs and Coxeter groups
- Coloring -colorable graphs using relatively small palettes
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
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Computing the permanent of (some) complex matrices
- 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
- On the zeroes of hypergraph independence polynomials
- Edge-reflection positivity and weighted graph homomorphisms
- 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)
