Генерация графов с тривиальными автоморфизмами

14

Я пересматриваю некоторую криптографическую модель. Чтобы показать его неадекватность, я разработал искусственный протокол, основанный на изоморфизме графа.

Это «обычное дело» (еще спорный!) Предположить существование BPP алгоритмов способны генерировать «жесткие экземпляры проблемы Изоморфизма графов.» (Вместе со свидетелем изоморфизма.)

В моем надуманном протоколе я предполагаю существование таких алгоритмов BPP, которые удовлетворяют одному дополнительному требованию:

  • Пусть сгенерированные графы будут и G 2 . Есть только один свидетель (перестановка), который отображает G 1 в G 2 .грамм1грамм2грамм1грамм2

Это означает, что имеет только тривиальные автоморфизмы . Другими словами, я предполагаю существование некоторого алгоритма BPP, который работает следующим образом:грамм1

  1. На входе сгенерируем n- вершинный граф G 1 так , чтобы он имел только тривиальные автоморфизмы.1NNграмм1
  2. Выберите случайную перестановку над [ nπ[N]знак равно{1,2,...,N}грамм1грамм2
  3. грамм1,грамм2,π

Я предполагаю, что на шаге 1 грамм1грамм1,грамм2

Мое предположение разумно? Может ли кто-нибудь указать мне некоторые ссылки?

М.С. Дусти
источник
1
Просто некоторая альтернативная терминология: граф, единственным автоморфизмом которого является тождество, часто называют жестким графом. Может помочь в поиске ...
Джозеф О'Рурк
@ Джозеф: Спасибо. Это обязательно поможет!
MS Dousti 8.10.10

Ответы:

9

По крайней мере, первый наивный подход, о котором можно подумать, не работает. Подход, который я имею в виду, состоит в том, чтобы просто генерировать чисто случайно. Поскольку почти все графы не имеют симметрий (то есть доля графов на n вершинах без нетривиальных автоморфизмов приближается к 1 при n грамм1NNграмм1

Но у второго наивного подхода есть шанс сработать: сгенерировать случайный регулярный граф (непостоянной степени, поскольку изоморфизм графов постоянной степени находится в P). Это также не имеет нетривиальных автоморфизмов с высокой вероятностью [KSV], но результат Бабая-Кучеры неприменим (как они указывают в статье). Доказательство того, что это неуязвимый генератор, очевидно, требует некоторых предположений, но можно представить, что безоговорочно доказывают, что изоморфизм регулярных графов среднего случая так же труден, как изоморфизм графов наихудшего случая, хотя я не знаю, насколько это вероятно. (Обратите внимание, что изоморфизм регулярных графов в худшем случае эквивалентен изоморфизму (в общем случае) графа в худшем случае.)

[BK]. Ласло Бабай, Людик Кучера, Каноническая маркировка графиков по линейному среднему времени . ФОКС 1979, с.39-46.

[KSV] Чжон Хан Ким, Бенни Судаков и Ван Х. Ву. Об асимметрии случайных регулярных графов и случайных графов . Случайные структуры и алгоритмы, 21 (3-4): 216-224, 2002. Также доступно здесь .

Джошуа Грохов
источник
1
Спасибо, Джошуа. У меня есть один вопрос. Цитата: «Изоморфизм регулярного графа наихудшего случая эквивалентен изоморфизму (общему) графа наихудшего случая». Означает ли это, что при наличии оракула, который решает изоморфизм регулярных графов, можно решить изоморфизм графов наихудшего случая (общего) за полиномиальное время? Можете ли вы дать мне несколько указателей?
MS Dousti 9.10.10
Это именно то, что это значит. Конструкция не так уж сложна. Вот ссылка; Я не знаю, является ли это первым: dx.doi.org/10.1016/0022-0000(79)90043-6 также доступен по адресу cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf
Джошуа