Complexity of surjective homomorphism problem to reﬂexive cycles

Korchagin Nikita Pavlovich

Complexity of surjective homomorphism problem to reﬂexive cycles

Korchagin N. P.

Korchagin Nikita Pavlovich

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

Published: 2023, vol. 27, issue 4, pp. 40–61

Download full text (In Russian)

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 reﬂexive 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.

BibTeX

@article{IS-Korchagin2023,
  author  = {Korchagin, Nikita Pavlovich},
  title   = {{Complexity of surjective homomorphism problem to reﬂexive cycles}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2023},
  volume  = {27},
  number  = {4},
  pages   = {40--61},
}

AMSBIB

\Bibitem{IS-Korchagin2023}
\by N.\,P.~Korchagin
\paper Complexity of surjective homomorphism problem to reﬂexive cycles
\jour Intelligent Systems. Theory and Applications
\yr 2023
\vol 27
\issue 4
\pages 40--61
\lang In Russian

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

← Back to issue