ECCC-Report TR05-121https://eccc.weizmann.ac.il/report/2005/121Comments and Revisions published for TR05-121en-usFri, 28 Oct 2005 09:15:22 +0200
Paper TR05-121
| On counting homomorphisms to directed acyclic graphs |
Martin Dyer,
Leslie Ann Goldberg,
Michael S. Paterson
https://eccc.weizmann.ac.il/report/2005/121We 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.
Fri, 28 Oct 2005 09:15:22 +0200https://eccc.weizmann.ac.il/report/2005/121