This article is cited in 2 papers

Part 2. Special Issues in Intellectual Systems Theory

Complexity of surjective homomorphism problem to reflexive cycles

N. P. Korchagin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: In this article we explore the complexity of the decision problem which takes a graph as an input and asks, if there is a surjective homomorphism from it to some fixed graph $G$. We prove, that if $G$ is a reflexive cycle with $7$ or more vertices, then this problem is $NP$-hard. The proof is based on a novel approach, which enables reduction of a constraint satisfaction problem to the problem of satisfying a system of equations, which, in turn, is reduced to solving surjective constraint satisfaction problem.

Keywords: surjective homomorphisms, computation complexity, constraint satisfaction, polymorphisms