Part 3. Mathematical models

The complexity of the graph homomorphism problem on mixed reflexive cycles

N. P. Korchagin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The surjective graph homomorphism problem $Surj-Hom(H)$ is a problem of deciding whether a given graph allows vertex-surjective homomorphism to a fixed graph $H$. In this paper we study the $Surj-Hom$ problem for cyclic graphs which are obtained from undirected cycles by assigning direction to some edges and in which each vertex contains a loop. We explore the $Surj-Hom$ problem in its conjunction with the surjective constraint satisfaction problem $SCSP$. We define a property which allows to obtain the complexity of the SCSP problem for some predicates via reduction. We implement this property to determine the complexity of the $Surj-Hom$ problem for all desired cycles except for three cycles with $4$, $5$ and $6$ vertices.

Keywords: surjective graph homomorphism, computational complexity, constraint satisfaction, polymorphism.