Abstract:
We give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. $H$ is a fixed directed acyclic graph. The problem is, given an input digraph $G$, how many homomorphisms are there from $G$ to $H$. We give a graph-theoretic classification, showing that for some digraphs $H$, the problem is in P and for the rest of the digraphs $H$ the problem is \#P-complete. An interesting feature of the dichotomy, which is absent from related dichotomy results, is that there is a rich supply of tractable graphs~$H$ with complex structure.