График автоморфизм является перестановкой узлов графа , который индуцирует биекцию на множество ребер . Формально, это - перестановка узлов, таких тогда и только тогда, когдаf ( u , v ) ∈ E ( f ( u ) , f ( v ) ) ∈ E
Определите нарушенное ребро для некоторой перестановки как ребро, которое отображается на не ребро, или ребро, прообраз которого не является ребром.
Вход : нежесткий граф
Проблема : Найти (не тождественную) перестановку, которая минимизирует количество нарушенных ребер.
Какова сложность нахождения (не тождественной) перестановки с минимальным количеством нарушенных ребер? Сложна ли задача для графов с ограниченной максимальной степенью (в предположении некоторой сложности)? Например, это сложно для кубических графов?
Мотивация: Проблема заключается в релаксации задачи автоморфизма графа (GA). Входной граф может иметь нетривиальный автоморфизм (например, нежесткий граф). Насколько сложно найти приближенный автоморфизм (перестановочный шкаф)?
Изменить 22 апреля
Жесткий (асимметричный) граф имеет только тривиальный автоморфизм. Нежесткий граф имеет некоторую (ограниченную) симметрию, и я хотел бы понять сложность аппроксимации его симметрии.
источник
Ответы:
Показатель сложности - это количество зондов в матрицах смежности, и цель состоит в том, чтобы различать два случая с высокой вероятностью, используя сублинейное число зондов.
Эльдар Фишер и Арье Мацлия ( спасибо, Арнаб ) написали статью в SODA 2006 именно об этой проблеме. Хотя это не имеет прямого отношения к вашей проблеме, оно может стать способом постановки возможной проблемы и даже может предоставить вам полезные методы.
источник
Результат Юджина Лукса (« Изоморфизм графов ограниченной валентности может быть проверен за полиномиальное время ») показывает, что изоморфизм (или автоморфизм) графов для графов ограниченной степени находится за полиномиальное время. Следовательно, если вы ищете некоторый (не тождественный, как указывал Юкка) почти автоморфизм для кубических графов, которые не являются жесткими, то мы можем использовать алгоритм Лукса и взять любой нетривиальный автоморфизм в графе.
источник