Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-121 | 17th October 2005 00:00

On counting homomorphisms to directed acyclic graphs

RSS-Feed




TR05-121
Authors: Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson
Publication: 28th October 2005 09:15
Downloads: 3349
Keywords: 


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.



ISSN 1433-8092 | Imprint