Abstract
The complexity of graph homomorphism problems has been the subject of intense study for some years. In this paper, we prove a decidable complexity dichotomy theorem for the partition function of directed graph homomorphisms. Our theorem applies to all non-negative weighted forms of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function ZA(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability on the other hand is algebraic and based on properties of polynomials.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.A. Bulatov (2013). The Complexity of the Counting Constraint Satisfaction Problem. Journal of the ACM 60(5), 34:1–34:41.
Bulatov, A.A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. Information and Computation 205(5), 651–678 (2007)
Bulatov, A.A., Dyer, M.E., Goldberg, L.A., Jalsenius, M., Jerrum, M.R., Richerby, D.: The complexity of weighted and unweighted #CSP. Journal of Computer and System Sciences 78(2), 681–688 (2012)
Bulatov, A.A., Grohe, M.: The complexity of partition functions. Theoretical Computer Science 348(2), 148–186 (2005)
Andrei A. Bulatov (2008). The Complexity of the Counting Constraint Satisfaction Problem. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming, 646–661.
J.-Y. Cai & X. Chen (2010). A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. In Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science, 437–446.
J.-Y. Cai & X. Chen (2012). Complexity of Counting CSP with Complex Weights. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, 909–920.
J.-Y. Cai, X. Chen & P. Lu (2011). Nonnegatively weighted #CSPs: An effective complexity dichotomy. In Proceedings of the 25th IEEE Conference on Computational Complexity, 45–54.
Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: A dichotomy theorem. SIAM Journal on Computing 42(3), 924–1029 (2013a)
J.-Y. Cai, H. Guo & T. Williams (2013b). A Complete Dichotomy Rises from the Capture of Vanishing Signatures: Extended Abstract. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 635–644.
J.-Y. Cai, H. Guo & T. Williams (2014). The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, 601–610.
M.E. Dyer, L.A. Goldberg & M. Paterson (2007). On counting homomorphisms to directed acyclic graphs. Journal of the ACM 54(6), Article 27.
Dyer, M.E., Greenhill, C.: The complexity of counting graph homomorphisms. Random Structures & Algorithms 17(3–4), 260–289 (2000)
M.E. Dyer & D. Richerby (2010). On the Complexity of #CSP. In Proceedings of the 42nd ACM Symposium on Theory of Computing, 725–734.
Dyer, M.E., Richerby, D.: An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing 42(3), 1245–1274 (2013)
Feder, T., Vardi, M.Y.: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing 28(1), 57–104 (1999)
Freedman, M., Lovász, L., Schrijver, A.: Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society 20, 37–51 (2007)
Goldberg, L.A., Grohe, M., Jerrum, M., Thurley, M.: A complexity dichotomy for partition functions with mixed signs. SIAM Journal on Computing 39(7), 3336–3402 (2010)
M. Grohe & M. Thurley (2011). Counting homomorphisms and partition functions. In Model Theoretic Methods in Finite Combinatorics, M. Grohe & J. Makowsky, editors, Contemporary Mathematics, Vol. 558, 243–292. American Mathematical Society.
Hell, P., Nešetřil, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48(1), 92–110 (1990)
P. Hell & J. Nešetřil (2004). Graphs and Homomorphisms. Oxford University Press.
H.W. Lenstra (1992). Algorithms in Algebraic Number Theory. Bulletin of the American Mathematical Society 26(2).
M. Thurley (2009). The complexity of partition functions. PhD Thesis, Humboldt Universitat zu Berlin.
Acknowledgements
We would like to thank the following colleagues for their interest and helpful comments: Martin Dyer, Alan Frieze, Leslie Ann Goldberg, Richard J. Lipton, Pinyan Lu, Mike Paterson, Marc Thurley, and Leslie Valiant.
A preliminary version of the paper appeared in Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science in 2010. Research of Jin-Yi Cai was supported by NSF grants CCF-0830488 and CCF-0914969. Part of the research of Xi Chen was supported by NSF grants CCF-0832797 and DMS-0635607 while he was a postdoc at Princeton University and University of Southern California.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Cai, JY., Chen, X. A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. comput. complex. 28, 345–408 (2019). https://doi.org/10.1007/s00037-019-00184-5
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-019-00184-5