Я работаю над проблемой, связанной с латинскими квадратами, и я хочу метод, который сводится к решению проблемы:
Входные данные : конечный простой граф G.
Выходные данные : YES
если G имеет нетривиальный автоморфизм, в NO
противном случае.
Следовательно ...
Вопрос : существует ли эффективный алгоритм определения того, имеет ли граф нетривиальный автоморфизм?
Мы могли бы использовать Nauty или Bliss (и, возможно, некоторые другие пакеты) для вычисления всей группы автоморфизмов, но мне это не нужно; все, что мне нужно, чтобы определить, является ли это тривиальным или нет.
Возможно, что эта проблема решения теоретически эквивалентна по сложности, чтобы «вычислить всю группу автоморфизмов» каким-то образом. Я не уверен.
Для моей цели «эффективный» в основном означает «быстрее на практике, чем вычисление всей группы автоморфизмов», но я также интересуюсь теорией, стоящей за этим.
источник
Ответы:
Поскольку вас также интересует теория, лежащая в ее основе, я бы дал вам квазиполиномиальный алгоритм времени для вашей задачи.
Для каждой пары вершинты ≠ в (той же степени) в г мы пытаемся выяснить, можно ли поменять местами U и v .
Для этого сделайте копиюг , назовите ее г' . Теперь удалите U из г , удалите (копию) v из г' .
Тогда для каждогоw ∈ N( и ) приложите к нему очень длинный путь, но только полиномиально длинный .
Тогда для каждого (экземпляра)w ∈ N( С о р у о ф v ) присоедините к нему очень длинный путь, но только полиномиально длинный .
Все упомянутые выше очень длинные пути, но полиномиально длинные , должны быть одинаковой длины.
Вызовите алгоритм Бабая на входе этой вновь созданной пары графиков.
Если для любой пары( U , V ) у нас есть ответ YЕS от Бабая, ответьте YЕS и остановитесь.
Если никто не возвращает ответYЕS , ответьте NО и остановитесь.
Очевидно, что присоединение ко всем вершинам вN( и ) и N( v ) заставляет изоморфизм графов внутреннего рабочего механизма Бабая его алгоритма отображать только вершины из N( и ) в N( v ) . Таким образом, если ответ Бабай является YЕS , то можно смело подключать сзади U и v имеют нетривиальный автоморфизм г , так как г' является копией г .
Сложность во время выполнения все еще квазиполична.
источник