Я не обладаю знаниями в области теории сложности с участием групп, поэтому я прошу прощения, если это хорошо известный результат.
Вопрос 1. Пусть - простой неориентированный граф порядка n . Какова вычислительная сложность (с точки зрения n ) определения, если G вершинно-транзитивным?
Напомним, что граф является вершинно-транзитивным, если A u t ( G ) действует транзитивно на V ( G ) .
Я не уверен, допускает ли приведенное выше определение алгоритм полиномиального времени, поскольку может быть так, что порядок экспоненциальный.
Однако вершинно-транзитивные графы имеют некоторые другие структурные свойства, которые можно использовать для их эффективного определения, поэтому я не уверен, каков статус вышеуказанного вопроса.
Другим интересным подклассом вершинно-транзитивных графов, который имеет еще большую структуру, является класс графов Кэли . Поэтому естественно также поставить следующий связанный вопрос
Вопрос 2. Какова вычислительная сложность определения, если граф является графом Кэли?
Ответы:
У меня нет полного ответа, но я думаю, что обе проблемы открыты.
Статья Jajcay, Malnič, Marušič [3] связана с вашим первым вопросом. Они предоставляют некоторые инструменты для проверки вершинной транзитивности. Во введении говорится, что:
Обратите внимание, что тест вершинной транзитивности может быть выполнен путем проверки изоморфизма графа раз. Сделайте две копии G и G ′ вашего графа со специальными якорями (такими как пути длины n + 1 ) в u ∈ V ( G ) и v ∈ V ( G ′ ) . Существует изоморфизм между G и G ′ тогда и только тогда, когда исходный граф имеет автоморфизм, отображающий u в v . Таким образом, вы можете проверить вершинную склонность, зафиксировав вершинуn−1 G G′ n+1 u∈V(G) v∈V(G′) G G′ u v x и проверка, что существуют автоморфизмы, отображающие x на все остальные вершины.
Также обратите внимание, что если тест вершинной транзитивности может быть выполнен за полиномиальное время, то такой же будет тест изоморфизма вершинно-транзитивных графов. Это потому, что два вершинно-транзитивных графа изоморфны тогда и только тогда, когда их непересекающееся объединение вершинно-транзитивно. Я считаю, что сложность изоморфизма графов для вершинно-транзитивных графов неизвестна.
По второму вопросу я нашел частичный результат. Циркулянт график представляет собой график Кэлей на циклическую группу. Евдокимов и Пономаренко [2] показывают, что распознавание циркулянтных графов может быть сделано за полиномиальное время. Также вам будет интересна глава книги Алспаха [1, глава 6: графы Кэли, раздел 6.2: распознавание], хотя в ней говорится, что:
источник