Тестирование изоморфизма асимметричных графов

При чтении вопрос примеров , где единственность решения делает его легче найти , новый (? Проще) возник вопрос , на мой взгляд: на самом деле мы не знаем , если Изоморфизм графов ( проблема) в . $GI$ $P$

Но что произойдет, если мы предположим, что оба $G_1$ и асимметричны (т.е. оба имеют только тривиальный (тождественный) автоморфизм)? Проблема становится легче (полиномиальное время)? $G_2$

Примечание: проблема не может быть сложнее, чем автоморфизм графов ( ), потому что есть быстрое сокращение: просто используйте на , если ответ да, тогда эти два графа изоморфны (см. Также Йоханнес Коблер, Уве Шенинг, Якобо Торан: Изоморфизм графа мал для пп . 401-411). $GA$ $GA$ $G_1 \cup G_2$

reference-request graph-isomorphism Марцио де Биаси
источник

С вероятностью, приближающейся к 1 с ростом n, ваш граф имеет только тривальный автоморфизм по колмогоровской сложности.

Чад Brewbaker

+1 Хороший вопрос, ваш вопрос потенциально приводит к нападению на P против NP. Попытайтесь доказать, что не существует сокращения Тьюринга от

к вашей проблеме.

G A

$GA$

Мухаммед Аль-Туркистани

Эта проблема известна как проблема изоморфизма жестких графов. Если это может быть решено в полиномиальное время или нет, широко открыто. Существует некоторая работа, пытающаяся атаковать его с помощью квантовых алгоритмов, например, сводя ее к проблеме скрытого сдвига ( arxiv.org/abs/quant-ph/0510185 ), но результаты в основном отрицательные, показывающие, что проверенные методы не Работа.

Матеус де Оливейра Оливейра

Любой граф можно сделать жестким, чтобы он имел только один эндоморфизм (и, следовательно, автоморфизм), прикрепив взаимно жесткие графы к каждой вершине. Это подразумевает редукцию Тьюринга из GI к решению изоморфизма асимметричных графов. Увы, это не полином.

Андрас Саламон

Ну, Чайлдс / Вочан не одиноки в использовании жестких обозначений графов с одним автоморфизмом. В 1994 году в Бабае было проведено исследование, в котором уже указывается, что терминология не соответствует стандарту www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf. Также в наше время это жесткое слово было использовано в этом смысле Якобо Тораном ( uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf ). Так что, похоже, вопрос в том, заботится ли автор о вложениях или нет. Но я использовал асимметричность в своем ответе, чтобы избежать путаницы.

Матеус де Оливейра Оливейра

По запросу Марцио Де Биаси я превращаю свой комментарий в ответ.

Граф асимметричен (некоторые авторы называют его жестким), если он обладает уникальным автоморфизмом, т. Е. Тождеством. Как указал Чед Брюбакер, большинство графиков асимметричны. Однако открыты следующие два вопроса:

1) Является ли изоморфизм асимметричных графов в P?

2) Можно ли свести изоморфизм общих графов к изоморфизму асимметричных графов?

$\Omega(n\log n)$

Матеус де Оливейра Оливейра
источник

Тестирование изоморфизма асимметричных графов

Ответы: