The complexity of the graph homomorphism problem on mixed reflexive
cycles

Korchagin Nikita Pavlovich

The complexity of the graph homomorphism problem on mixed reflexive cycles

Korchagin N. P.

Korchagin Nikita Pavlovich

postgraduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Published: 2025, vol. 29, issue 4, pp. 102–134

Download full text (In Russian)

Abstract

The surjective graph homomorphism problem \(\mbox{Surj-Hom}(\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 \(\mbox{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 \(\mbox{Surj-Hom}\) problem in its conjunction with the surjective constraint satisfaction problem \(\mbox{SCSP}\). We define a property which allows to obtain the complexity of the \(\mbox{SCSP}\) problem for some predicates via reduction. We implement this property to determine the complexity of the \(\mbox{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.

BibTeX

@article{IS-Korchagin2025,
  author  = {Korchagin, Nikita Pavlovich},
  title   = {{The complexity of the graph homomorphism problem on mixed
reflexive cycles}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {4},
  pages   = {102--134},
}

AMSBIB

\Bibitem{IS-Korchagin2025}
\by N.\,P.~Korchagin
\paper The complexity of the graph homomorphism problem on mixed
reflexive cycles
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 4
\pages 102--134
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue