This article is cited in 1 paper

The complexity of the graph homomorphism problem on directed reflexive cycles

N. P. Korchagin

Lomonosov Moscow State University

Abstract: The surjective graph homomorphism problem SCSP($\mathcal{H}$) is a problem of deciding whether a given graph allows vertex-surjective homomorphism to a fixed graph $\mathcal{H}$. In this paper we study the Surj-Hom problem for cycles in which each edge is directed and each vertex contains a loop. We explore this problem in its connection to the surjective contraint satisfaction problem SCSP. We present a property, which ties the complexity of SCSP over a constraint language $\Gamma$ to the structure of polymorphisms of $\Gamma$. We use this property to determine the complexity of Surj-Hom for all directed reflexive cycles except for a single hexagon.

Keywords: surjective graph homomorphism, computational complexity, constraint satisfaction, polymorphism, many-sorted predicate.

UDC: 519.161

Received: 19.02.2025

DOI: 10.4213/dm1868