Эта публикация цитируется в 1 статье

Сложность задачи о существовании сюръективного гомоморфизма на ориентированные рефлексивные циклы

Н. П. Корчагин

МГУ имени М. В. Ломоносова

Аннотация: Для графа $\mathcal{H}$ в задаче о существовании сюръективного гомоморфизма ($\operatorname{Surj-Hom}(\mathcal{H})$) по данному графу $\mathcal{G}$ требуется определить, существует ли сюръективный гомоморфизм из $\mathcal{G}$ на $\mathcal{H}$. В статье изучается сложность задачи Surj-Hom для циклов, в которых каждое ребро ориентировано ровно в одном направлении, а каждая вершина содержит петлю. Мы рассматриваем Surj-Hom как частный случай задачи о сюръективном удовлетворении ограничениям (SCSP). Мы вводим свойство, которое связывает сложность SCSP на множестве ограничений $\Gamma$ со структурой полиморфизмов $\Gamma$, и используем это свойство, чтобы определить сложность задачи Surj-Hom для всех ориентированных рефлексивных циклов, кроме единственного цикла с шестью вершинами.

Ключевые слова: сюръективный гомоморфизм графов, сложность вычислений, удовлетворение ограничениям, полиморфизм, многоосновной предикат.

УДК: 519.161

Статья поступила: 19.02.2025

DOI: 10.4213/dm1868