Существует ли эффективный алгоритм определения того, имеет ли граф нетривиальный автоморфизм?

Я работаю над проблемой, связанной с латинскими квадратами, и я хочу метод, который сводится к решению проблемы:

Входные данные : конечный простой граф G.
Выходные данные : YESесли G имеет нетривиальный автоморфизм, в NOпротивном случае.

Следовательно ...

Вопрос : существует ли эффективный алгоритм определения того, имеет ли граф нетривиальный автоморфизм?

Мы могли бы использовать Nauty или Bliss (и, возможно, некоторые другие пакеты) для вычисления всей группы автоморфизмов, но мне это не нужно; все, что мне нужно, чтобы определить, является ли это тривиальным или нет.

Возможно, что эта проблема решения теоретически эквивалентна по сложности, чтобы «вычислить всю группу автоморфизмов» каким-то образом. Я не уверен.

Для моей цели «эффективный» в основном означает «быстрее на практике, чем вычисление всей группы автоморфизмов», но я также интересуюсь теорией, стоящей за этим.

algorithms graphs graph-theory reference-request Ребекка Дж. Стоунс
источник

Это эквивалентно изоморфизму графа.

Юваль Фильмус

@YuvalFilmus Насколько мне известно, не существует известного сокращения от "Является ли

изоморфным

" до "Имеет ли

нетривиальный автоморфизм". Очевидно, что если

то их непересекающееся объединение имеет нетривиальный автоморфизм (перестановка

), но любой нетривиальный автоморфизм группы

также будет нетривиальным автоморфизмом группы

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

G_{1} ≃ G_{2}

$G_1\simeq G_2$

G_{1}

$G_1$

G_{2}

$G_2$

G_{1}

$G_1$

G_{1} + G_{2}

$G_1+G_2$

Дэвид Ричерби

Относительно вашего последнего вопроса: если дать оракула GA, можно за полиномиальное время найти порождающее множество группы автоморфизмов, то GI сводится по Тьюрингу к GA, что, я не уверен, известно.

Ариэль

@DavidRicherby Как насчет следующей статьи? sciencedirect.com/science/article/pii/…

Юваль Фильмус

@YuvalFilmus Хорошо, значит, вы используете сокращения Тьюринга, а я использую сокращение один-один. И я думаю, что сокращения Тьюринга более актуальны для тех, кто на самом деле пытается решить проблему.

Дэвид Ричерби

Ответы:

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

Для каждой пары вершин $u\neq v$ (той же степени) в $G$ мы пытаемся выяснить, можно ли поменять местами $u$ и $v$ .

Для этого сделайте копию $G$ , назовите ее $G'$ . Теперь удалите $u$ из $G$ , удалите (копию) $v$ из $G'$ .

Тогда для каждого $w\in N(u)$ приложите к нему очень длинный путь, но только полиномиально длинный .

Тогда для каждого (экземпляра) $w\in N(copy\ of\ v)$ присоедините к нему очень длинный путь, но только полиномиально длинный .

Все упомянутые выше очень длинные пути, но полиномиально длинные , должны быть одинаковой длины.

Вызовите алгоритм Бабая на входе этой вновь созданной пары графиков.

Если для любой пары $(u, v)$ у нас есть ответ $YES$ от Бабая, ответьте $YES$ и остановитесь.

Если никто не возвращает ответ $YES$ , ответьте $NO$ и остановитесь.

Очевидно, что присоединение ко всем вершинам в $N(u)$ и $N(v)$ заставляет изоморфизм графов внутреннего рабочего механизма Бабая его алгоритма отображать только вершины из $N(u)$ в $N(v)$ . Таким образом, если ответ Бабай является $YES$ , то можно смело подключать сзади $u$ и $v$ имеют нетривиальный автоморфизм $G$ , так как $G'$ является копией $G$ .

Сложность во время выполнения все еще квазиполична.

Тхин Д. Нгуен
источник