Counting homomorphisms in plain exponential time

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2019-04-09
Authors/Contributors
Abstract
In the counting Graph Homomorphism problem GraphHOM the question is: Given graphs G, H, find the number of homomorphisms from G to H. This problem is generally #P-complete, moreover, Cygan et al. proved that unless the Exponential Time Hypothesis fails there is no algorithm that solves this problem in plain exponential time. This, however, does not rule out the possibility that faster algorithms exist for restricted problems of this kind. Wahlstrom proved that #GraphHOM can be solved in plain exponential time, provided H has clique width k. We generalize this result to a larger class of graphs, and also identify several other graph classes that admit a plain exponential algorithm for # GraphHOM.
Identifier
etd20159
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Bulatov, Andrei
Member of collection
Model
English