On counting homomorphisms to directed acyclic graphs
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.
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|
|Editor:||Bugliesi, M and Preneel, B and Sassone, V and Wegener, I|
|Number of Pages:||12|
|Page Range:||pp. 38-49|
|Title of Event:||33rd International Colloquium on Automata, Languages and Programming|
|Location of Event:||Venice, ITALY|
|Date(s) of Event:||JUL 10-14, 2006|
Actions (login required)