EN
Сложность задачи о существовании сюръективного гомоморфизма на смешанно-ориентированные рефлексивные циклы
Опубликована: 2025 год, том 29, выпуск 4, С. 102–134
Аннотация
Для графа \(\mathcal{H}\) в задаче \(\mbox{Surj-Hom}(\mathcal{H})\) по данному графу \(\mathcal{G}\) требуется определить, существует ли сюръективный гомоморфизм из \(\mathcal{G}\) на \(\mathcal{H}\). В данной работе мы изучаем сложность задачи \(\mbox{Surj-Hom}\) для графов, которые получаются из неориентированных циклов добавлением ориентации некоторым рёбрам, и в которых каждая вершина содержит петлю.
Мы рассматриваем задачу \(\mbox{Surj-Hom}\) как частный случай массовой задачи сюръективного удовлетворения ограничениям \(\mbox{SCSP}\). Мы вводим свойство, которое позволяет определять сложность \(\mbox{SCSP}\) с помощью сведения. Мы используем это свойство и определяем сложность \(\mbox{Surj-Hom}\) для всех рассматриваемых циклов, кроме трёх циклов длины \(4\), \(5\) и \(6\).
Ключевые слова: cюръективный гомоморфизм графов, сложность вычислений, удовлетворение ограничениям, полиморфизм.
BibTeX
@article{IS-Korchagin2025,
author = {Корчагин, Никита Павлович},
title = {{Сложность задачи о существовании сюръективного гомоморфизма на
смешанно-ориентированные рефлексивные циклы}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2025},
volume = {29},
number = {4},
pages = {102--134},
}
AMSBIB
\RBibitem{IS-Korchagin2025}
\by Н.\,П.~Корчагин
\paper Сложность задачи о существовании сюръективного гомоморфизма на
смешанно-ориентированные рефлексивные циклы
\jour Интеллектуальные системы. Теория и приложения
\yr 2025
\vol 29
\issue 4
\pages 102--134