Dyer, Martin, Goldberg, Leslie Ann and Paterson, Michael S. (2007) On counting homomorphisms to directed acyclic graphs. Journal of the ACM, Vol.54 (No.6). Article: 27. doi:10.1145/1314690.1314691 ISSN 0004-5411.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes that lie strictly between them. Thus, if P not equal NP, it is not possible to classify NP using any finite collection of complexity classes. This situation has led to attempts to identify smaller classes of problems within NP where dichotomy results may hold: every problem is either in P or is NP-complete. A similar situation exists for counting problems. If P not equal# P, there is an infinite hierarchy in between and it is important to identify subclasses of # P where dichotomy results hold. Graph homomorphism problems are a fertile setting in which to explore dichotomy theorems. Indeed, Feder and Vardi have shown that a dichotomy theorem for the problem of deciding whether there is a homomorphism to a fixed directed acyclic graph would resolve their long-standing dichotomy conjecture for all constraint satisfaction problems. In this article, we give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. Let H be a fixed directed acyclic graph. The problem is, given an input digraph G, determine how many homomorphisms there are 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 previously known dichotomy results, is that there is a rich supply of tractable graphs H with complex structure.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Journal of the ACM
Publisher:	Association for Computing Machinery, Inc.
ISSN:	0004-5411
Official Date:	December 2007
Dates:	Date Event December 2007 Published
Volume:	Vol.54
Number:	No.6
Number of Pages:	23
Page Range:	Article: 27
DOI:	10.1145/1314690.1314691
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item