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 effcient algorithms for computing weighted sums approximating the number of k-colorings and the number of independent sets in a graph, as well as an effcient 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon and T.H. Marshall: Homomorphisms of edge-colored graphs and Coxeter groups, Journal of Algebraic Combinatorics 8 (1998), 5–13.
A. Barvinok: Computing the permanent of (some) complex matrices, Foundations of Computational Mathematics 16 (2016), 329–342.
A. Barvinok: Computing the partition function for cliques in a graph, Theory of Computing 11 (2015), 339–355.
P. Berman and M. Karpinski: On some tighter inapproximability results (extended abstract), Automata, languages and programming (Prague, 1999) 200-209, in: Lecture Notes in Computer Science, 1644, Springer, Berlin (1999).
B. Bukh: Personal communication, (2015).
A. Bulatov and M. Grohe: The complexity of partition functions, Theoretical Computer Science 348 (2005), 148–186.
J.-Y. Cai, X. Chen and P. Lu: Graph homomorphisms with complex values: a dichotomy theorem, SIAM Journal on Computing 42 (2013), 924–1029.
U. Feige and J. Kilian: Zero knowledge and the chromatic number, Journal of Computer and System Sciences 57 (1998), 187–199.
M.X. Goemans and D.P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association for Computing Machinery 42 (1995), 1115–1145.
E. Halperin, R. Nathaniel and U. Zwick: Coloring k-colorable graphs using relatively small palettes, Journal of Algorithms 45 (2002), 72–90.
J. Hästad: Clique is hard to approximate within n 1−ε, Acta Mathematica 182 (1999), 105–142.
D. Karger, R. Motwani and M. Sudan: Approximate graph coloring by semidefinite programming, Journal of the ACM 45 (1998), 246–265.
T.D. Lee and C.N. Yang: Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model, Physical Review (2) 87 (1952), 410–419.
L. Lovász: Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, 60, American Mathematical Society, Providence, RI, 2012.
D. Weitz: Counting independent sets up to the tree threshold, in: STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing 140-149, ACM, New York, 2006.
C.N. Yang and T.D. Lee: Statistical theory of equations of state and phase transitions. I. Theory of condensation, Physical Review (2) 87 (1952), 404–409.
D. Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number, Theory of Computing 3 (2007), 103–128.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Barvinok, A., Soberón, P. Computing the partition function for graph homomorphisms. Combinatorica 37, 633–650 (2017). https://doi.org/10.1007/s00493-016-3357-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-016-3357-2