Часть 3. Математические модели

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

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

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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

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