A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our …