Решение графа гомоморфизма

Решение гомоморфизма графа в общем случае является NP-полным.

Существуют ли какие-либо результаты, которые изучают эту проблему, когда лежащие в основе графы имеют алгебраическую структуру (например, выбор гомоморфизмов из графов смежных классов Кэли или Кэли в другие графы также с некоторой определенной структурой)? В дополнение к результатам сложности меня также интересуют полезные алгебраические и / или спектральные методы.

Если является классом графов с ограниченной шириной дерева, то проблема гомоморфизма из графов в G разрешима за полиномиальное время. Это может быть обобщено на более общее свойство «графов, ядро ​​которых имеет ограниченную длину дерева».$\mathcal{G}$$\mathcal{G}$

Грохе доказывает обратное: если ядра графов в имеют неограниченную трёхмерную ширину, то проблема гомоморфизма из G не решаема за полиномиальное время (при условии, что F P T ≠ W [ 1 ] ). Поэтому, если вы ограничите левый граф графами Кейли и т. Д., То имеет значение, имеют ли ядра ограниченную ширину дерева.$\mathcal{G}$$\mathcal{G}$$FPT\neq W[1]$

http://dl.acm.org/authorize?951212

Обратите внимание, что это не полностью отвечает на ваш вопрос: в результате Grohe предполагается, что правый граф является произвольным. Похоже, вас интересуют результаты, в которых правый граф также ограничен каким-то конкретным классом графов.

Определить, существует ли гомоморфизм графов, проще, чем подсчитать количество (взвешенных) гомоморфизмов графа.

Взвешенный случай

Для неориентированных целевых графов (т. Е. Числа гомоморфизмов взвешенных графов из входного графа G в H ) существует теорема о дихотомии.$H$$G$$H$

Джин-Йи Цай, Си Чен, Пиньян Лу. Гомоморфизмы графа с комплексными значениями. Теорема о дихотомии .

$H$

$H$$H$

$q$$q$$q$

Невзвешенный случай

Невзвешенный случай намного проще. Ниже я формулирую теорему 1.1 из следующей статьи.

Мартин Дайер, Кэтрин Грихилл. Сложность подсчета графа гомоморфизмов . (Также это прямая ссылка на бесплатный PDF.)

Теорема 1:

$H$$H$$H$