Dyer, Martin, Goldberg, Leslie Ann and Paterson, Michael S. (2006) On counting homomorphisms to directed acyclic graphs. In: 33rd International Colloquium on Automata, Languages and Programming, Venice, Italy, 10-14 Jul 2006. Published in: Lecture Notes in Computer Science, Volume 4051 pp. 38-49. ISBN 3-540-35904-4. ISSN 0302-9743. doi:10.1007/11786986_5

Research output not available from this repository, contact author.

Request Changes to record.

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, to 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, absent from related dichotomy results, is the rich supply of tractable graphs H with complex structure.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	3-540-35904-4
ISSN:	0302-9743
Editor:	Bugliesi, M and Preneel, B and Sassone, V and Wegener, I
Official Date:	2006
Dates:	Date Event 2006 Published
Volume:	Volume 4051
Number of Pages:	12
Page Range:	pp. 38-49
DOI:	10.1007/11786986_5
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	33rd International Colloquium on Automata, Languages and Programming
Type of Event:	Other
Location of Event:	Venice, Italy
Date(s) of Event:	10-14 Jul 2006

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