Counting, modular counting and graph homomorphisms

Thesis

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

We first study the problem #_kHomsToH of co...

Expand abstract

Authors: Magkakis, A

• DOI: 10.5287/ora-xqjndmmex
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: evolutionary dynamics; computational counting; graph homomorphisms; computational complexity
• Subjects: Computer science