Dyer, Martin, Goldberg, Leslie Ann and Paterson, Mike (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.

Full text not available from this repository.

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
Date:	2006
Volume:	Volume 4051
Number of Pages:	12
Page Range:	pp. 38-49
Identification Number:	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
URI:	http://wrap.warwick.ac.uk/id/eprint/33158

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item