The complexity of partition functions. (English) Zbl 1081.68030
Summary: We give a complexity-theoretic classification of the counting versions of so-called \(H\)-colouring problems for graphs \(H\) that may have multiple edges between the same pair of vertices. More generally, we study the problem of computing a weighted sum of homomorphisms to a weighted graph \(H\).
The problem has two interesting alternative formulations: first, it is equivalent to computing the partition function of a spin system as studied in statistical physics. And second, it is equivalent to counting the solutions to a constraint satisfaction problem whose constraint language consists of two equivalence relations.
In a nutshell, our result says that the problem is in polynomial time if the adjacency matrix of \(H\) has row rank 1, and # P-hard otherwise.
The problem has two interesting alternative formulations: first, it is equivalent to computing the partition function of a spin system as studied in statistical physics. And second, it is equivalent to counting the solutions to a constraint satisfaction problem whose constraint language consists of two equivalence relations.
In a nutshell, our result says that the problem is in polynomial time if the adjacency matrix of \(H\) has row rank 1, and # P-hard otherwise.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C15 | Coloring of graphs and hypergraphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | Bulatov, A.; Dalmau, V., Towards a dichotomy theorem for the counting constraint satisfaction problem, (Proc. 44th IEEE Symp. on Foundations of Computer Science, FOCS’03 (2003)), 562-571 · Zbl 1115.68141 |
| [2] | Bulatov, A. A., A dichotomy theorem for constraints on a three-element set, (Proc. 43rd IEEE Symp. on Foundations of Computer Science, FOCS’02 (2002)), 649-658 |
| [3] | Bulatov, A. A., Tractable conservative constraint satisfaction problems, (Proc. 18th Ann. IEEE Symp. on Logic in Computer Science (2003)), 321-330 |
| [4] | Creignou, N.; Hermann, M., Complexity of generalized satisfiability counting problems, Inform. Comput., 125, 1, 1-12 (1996) · Zbl 0853.68110 |
| [5] | Dyer, M.; Greenhill, C., The complexity of counting graph homomorphisms, Random Struct. Algorithms, 17, 260-289 (2000) · Zbl 0965.68073 |
| [6] | M.E. Dyer, L.A. Goldberg, M. Jerrum, Counting and sampling \(H\); M.E. Dyer, L.A. Goldberg, M. Jerrum, Counting and sampling \(H\) · Zbl 1028.68098 |
| [7] | Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput., 28, 57-104 (1998) · Zbl 0914.68075 |
| [8] | Goldberg, L. A.; Jerrum, M.; Paterson, M., The computational complexity of two-state spin systems, Random Struct. Algorithms, 23, 133-154 (2003) · Zbl 1030.82001 |
| [9] | Goldberg, L. A.; Kelk, S.; Paterson, M., The complexity of choosing an \(H\)-colouring (nearly) uniformly at random, (Proc. 34th ACM Symp. on Theory of Computing (2002)), 53-62 · Zbl 1192.68898 |
| [10] | Grotschel, M.; Lovasz, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1993), Springer: Springer Berlin · Zbl 0837.05001 |
| [11] | Hell, P.; Nešetřil, J., On the complexity of \(H\)-coloring, J. Combin. Theory Ser. B, 48, 92-110 (1990) · Zbl 0639.05023 |
| [12] | Hell, P.; Nešetřil, J.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. AMS, 348, 4, 1281-1297 (1996) · Zbl 0877.05055 |
| [13] | Jaeger, F.; Vertigan, D. L.; Welsh, D. J.A., On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc., 108, 35-53 (1990) · Zbl 0747.57006 |
| [14] | Jeavons, P. G.; Cohen, D. A.; Gyssens, M., Closure properties of constraints, J. ACM, 44, 4, 527-548 (1997) · Zbl 0890.68064 |
| [15] | Ko, K., Complexity Theory of Real Functions (1991), Birkhäuser: Birkhäuser Basel · Zbl 0791.03019 |
| [16] | Schaefer, T. J., The complexity of satisfiability problems, (Proc. 10th ACM Symp. on Theory of Computing (1978)), 216-226 · Zbl 1282.68143 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
