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, JUL 10-14, 2006. Published in: AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, 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 (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-35904-4
ISSN:	0302-9743
Editor:	Bugliesi, M and Preneel, B and Sassone, V and Wegener, I
Date:	2006
Volume:	4051
Number of Pages:	12
Page Range:	pp. 38-49
Identification Number:	10.1007/11786986_5
Publication Status:	Published
Title of Event:	33rd International Colloquium on Automata, Languages and Programming
Location of Event:	Venice, ITALY
Date(s) of Event:	JUL 10-14, 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