Premium
The complexity of counting graph homomorphisms
Author(s) -
Dyer Martin,
Greenhill Catherine
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200010/12)17:3/4<260::aid-rsa5>3.0.co;2-w
Subject(s) - homomorphism , mathematics , combinatorics , graph homomorphism , bipartite graph , discrete mathematics , bounded function , conjecture , graph , line graph , voltage graph , mathematical analysis
The problem of counting homomorphisms from a general graph G to a fixed graph H is a natural generalization of graph coloring, with important applications in statistical physics. The problem of deciding whether any homomorphism exists was considered by Hell and Nešetřil. They showed that decision is NP‐complete unless H has a loop or is bipartite; otherwise it is in P. We consider the problem of exactly counting such homomorphisms and give a similarly complete characterization. We show that counting is #P‐complete unless every connected component of H is an isolated vertex without a loop, a complete graph with all loops present, or a complete unlooped bipartite graph; otherwise it is in P. We prove further that this remains true when G has bounded degree. In particular, our theorems provide the first proof of #P‐completeness of the partition function of certain models from statistical physics, such as the Widom–Rowlinson model, even in graphs of maximum degree 3. Our results are proved using a mixture of spectral analysis, interpolation, and combinatorial arguments. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 260–289, 2000