Сложность распознавания вершинно-транзитивных графов

16

Я не обладаю знаниями в области теории сложности с участием групп, поэтому я прошу прощения, если это хорошо известный результат.

Вопрос 1. Пусть - простой неориентированный граф порядка n . Какова вычислительная сложность (с точки зрения n ) определения, если GGnnG вершинно-транзитивным?

Напомним, что граф является вершинно-транзитивным, если A u t ( G ) действует транзитивно на V ( G ) .GAut(G)V(G).

Я не уверен, допускает ли приведенное выше определение алгоритм полиномиального времени, поскольку может быть так, что порядок Aut(G) экспоненциальный.

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

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

Вопрос 2. Какова вычислительная сложность определения, если граф является графом Кэли?G

Jernej
источник
3
Несмотря на то, что группа автоморфизмов может быть суперэкспоненциальной, я думаю, что она может быть представлена ​​в полиномиальном пространстве, поскольку минимальное число образующих не более чем логарифмическое в |Aut(G)|
Тимоти Сан
2
Обратите внимание, что каждый вершинно-транзитивный граф является графом Кэли-Шриера: существует некоторая группа с порождающим множеством S и подгруппой H, такая, что вершинами графа являются смежные классы G / H , и два смежных класса связаны ребром, если некоторые элемент S переводит одно в другое. GSHG/HS
Джошуа Грохов
Связанный: mathoverflow.net/questions/156947/…
Питер Хейниг

Ответы:

14

У меня нет полного ответа, но я думаю, что обе проблемы открыты.


Статья Jajcay, Malnič, Marušič [3] связана с вашим первым вопросом. Они предоставляют некоторые инструменты для проверки вершинной транзитивности. Во введении говорится, что:

Для данного конечного графа решительно трудно определить, является ли Γ вершинно-транзитивным, и окончательный ответ обычно приходит только после того, как определена существенная часть полной группы автоморфизмов Γ .ΓΓΓ

Обратите внимание, что тест вершинной транзитивности может быть выполнен путем проверки изоморфизма графа раз. Сделайте две копии G и G вашего графа со специальными якорями (такими как пути длины n + 1 ) в u V ( G ) и v V ( G ) . Существует изоморфизм между G и G тогда и только тогда, когда исходный граф имеет автоморфизм, отображающий u в v . Таким образом, вы можете проверить вершинную склонность, зафиксировав вершинуn1GGn+1uV(G)vV(G)GGuvxи проверка, что существуют автоморфизмы, отображающие x на все остальные вершины.

Также обратите внимание, что если тест вершинной транзитивности может быть выполнен за полиномиальное время, то такой же будет тест изоморфизма вершинно-транзитивных графов. Это потому, что два вершинно-транзитивных графа изоморфны тогда и только тогда, когда их непересекающееся объединение вершинно-транзитивно. Я считаю, что сложность изоморфизма графов для вершинно-транзитивных графов неизвестна.


По второму вопросу я нашел частичный результат. Циркулянт график представляет собой график Кэлей на циклическую группу. Евдокимов и Пономаренко [2] показывают, что распознавание циркулянтных графов может быть сделано за полиномиальное время. Также вам будет интересна глава книги Алспаха [1, глава 6: графы Кэли, раздел 6.2: распознавание], хотя в ней говорится, что:

Мы будем игнорировать вычислительную проблему распознавания, является ли произвольный граф графом Кэли. Вместо этого мы всегда предполагаем, что графы Кэли были описаны в терминах групп, на которых они построены, вместе с наборами соединений. Для большинства проблем это не недостаток.


  1. Бейнеке, Уилсон, Кэмерон. Темы в алгебраической теории графов . Издательство Кембриджского университета, 2004.
  2. Евдокимов, Пономаренко. Циркулянтные графы: распознавание и тестирование изоморфизма за полиномиальное время. Санкт-Петербург Матем. J. 15 (2004) 813-835. DOI: 10,1090 / S1061-0022-04-00833-7
  3. Яйцай, Малнич, Марушич. О количестве замкнутых блужданий в вершинно-транзитивных графах. Дискретная математика 307 (2007) 484-493. DOI: 10.1016 / j.disc.2005.09.039
Йота Отачи
источник
4
n1xx