On counting homomorphisms to directed acyclic graphs
Dyer, Martin, Goldberg, Leslie Ann and Paterson, Mike. (2007) On counting homomorphisms to directed acyclic graphs. Journal of the ACM, Vol.54 (No.6). Article: 27. ISSN 0004-5411Full text not available from this repository.
Official URL: http://dx.doi.org/10.1145/1314690.1314691
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 > Computer Science|
|Journal or Publication Title:||Journal of the ACM|
|Publisher:||Association for Computing Machinery, Inc.|
|Number of Pages:||23|
|Page Range:||Article: 27|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)