«Крошечный» граф Изоморфизм

19

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

Предположим, что у нас есть машина Тьюринга за полиномиальное время которая на входе генерирует граф с узлами.1 n G M , n nM1nGM,nn

Мы можем определить проблему :ΠM

("Крошечный" GI): Учитывая граф , изоморфна ?G G M , | V |G=(V,E)GGM,|V|

Другими словами , мы должны сравнить данный график с «опорным» графа того же размера , генерируемого фиксированным многочленом времени машины Тьюринга .M

Для всех полиномиальных Тьюринга машины , мы имеем , и для многих из них мы имеем . Но так ли это для всех ? Проблема известна?Π MN P Π MP MMΠMNPΠMP
M

На первый взгляд, я подумал, что каждый должен быть намного проще, чем , потому что для каждого существует только один «эталонный» граф такого размера, и, возможно, симметрии / асимметрии графов, сгенерированных могут быть использованы и эффективны. может быть построен специальный тестер изоморфизма ... но это не так: может содержать своего рода универсальную синхронизирующую машину полиномиального времени, которая использует (унарный) ввод для генерации совершенно разных (в структуре) графов ссылок как увеличивается. G I n M M 1 n nΠMGInMM1nn

Марцио де Биаси
источник
Интересно, знаете ли вы пример P времени машина Тьюринга , которая генерирует график ? G M , NMGM,N
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany: тривиальный пример, для которого - это TM которая просто выводит изолированных вершин (или другая - это TM, которая выводит ). Без ограничения общности мы можем также думать о модели, в которой каждое полиномиальное время TM над двоичным алфавитом генерирует контрольный граф: просто выберите первые бита ленты после ее остановки и интерпретируйте ее как матрицу смежности . М п К п п 2 О М , пΠMPMnKnn2GM,n
Марцио Де Биаси
Для ТМ , что гарантирует , что имеет гамильтонов цикл, то я думаю не в . G M , n Π M PMGM,nΠMP
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany: Я думаю, что это неправда: просто выберите ТМ, который просто строит цикл из узлов: для всех опорный граф, который имеет гамильтонов цикл, легко проверяется за полиномиальное время. Я имею в виду нетривиальный пример (довольно простого) генератора, для которого кажется трудным показать, что проблема в ; но я хочу сделать некоторые тесты с Nauty, прежде чем добавить его к вопросу. n PnnP
Марцио Де Биаси,
1
Как насчет GI "Ицы Битцы", где для фиксированных M и N мы должны решить, одинаковы ли два графика, сгенерированные на 1 ^ n? (Это унарный язык.)
domotorp

Ответы:

6

[Это скорее несколько расширенных комментариев, чем ответ.]

1) Если , то не существует фиксированной полиномиальной оценки временной сложности всех , даже для , для которого требуется только время, скажем, : если за все время - , , то ниже приведен алгоритм поли-времени для GI. На входе создайте машину Тьюринга с часами, которые гарантируют, что никогда не будет работать более чем на шагов на входах размера , и таким образом, что , а затем решить за времяΠ M M n 3GIPΠMMn3 M Π MD T I M E ( n k ) ( G , H ) M G M G n 3 n M G ( 1 | V ( G ) | ) = G Π M G ( H ) O ( n k )n3 MΠMDTIME(nk)(G,H)MGMGn3nMG(1|V(G)|)=GΠMG(H)O(nk),

2) Так как для любого , не сложнее , чем GI, можно было бы подумать , что лучший результат по линии « , кажется , не в » можно было бы надеяться не является GI -полнота результата. Тем не менее, мне кажется маловероятным, что какой-либо из будет GI-завершен, по крайней мере по следующим причинам:Π M Π M P Π MMΠMΠMPΠM

  • Все известные мне результаты полноты GI относятся к довольно большим классам графов, а не к одному графу каждого размера. Даже если вы полностью отбросите требование к эффективности, я не знаю ни одного списка графиков , для которого (или даже ), так что проверка изоморфизма является GI-полной.| V ( G n ) | = n p o l y ( n ) G nG1,G2,|V(Gn)|=npoly(n)Gn

  • Относительно примечания, большинство (все?) Результатов GI-полноты представляют собой не просто сокращения «один-один», но имеют следующую форму: существует функция , которая дает экземпляр GI, является экземпляром другой GI-полной задачи. (Это просто многовременные морфизмы отношений эквивалентности или то, что Фортнау и я назвали «сокращениями ядра».) Мы можем легко показать безоговорочно, что такого сокращения от GI к любому (даже если вы измените определение, чтобы разрешить для вывода нескольких графиков.) Подсказка. Получите противоречие, показав, что любое такое должно полностью содержать свое изображение в .( G , H ) ( f ( G ) , f ( H ) ) Π M M f { G M , n } n 0f(G,H)(f(G),f(H))ΠMMf{GM,n}n0

3) Даже если можно построить на основе универсальной TM, как предложено в этом вопросе, возможно, все же можно создать эффективного тестера, но не эффективно. То есть, может быть , для каждого , в ?M Π M P / p o l yMMΠMP/poly

Джошуа Грохов
источник
1

У меня нет ответа на ваш вопрос, но я предлагаю рассмотреть более ограниченную версию для которой мы можем показать, что она лежит в P.ΠM

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

Ненаправленный граф с ребрами может быть описан длинной цепочкой , просто объединяющей элементы матрицы смежности в верхнем треугольнике. Следовательно, существует возможных графов на вершинах. Отсюда следует, что любая функция такая, что для всех описывает семейство графов. Для любой эффективно вычислимой такой функции мы определяем как н н 2 - нGn G2 n 2 - nn2n2G nf:NN0f(n)<2n2-n2n2n2nf:NN nfΠfGΠf0f(n)<2n2n2nfΠf

GΠfG is isomorph to the graph described by f(|V(G)|)

Для натурального числа пусть будет числом 1 в его двоичном представлении. Теперь рассмотрим для эффективно вычислимых функций для которых он содержит то есть семейства графов, для которых число ребер растет только логарифмически, как указано выше.xb1(x)Πff

b1(f(n))O(logn)

Покажем, что для этого класса функций находится в P.Πf

Пусть такая функция, а входной граф с вершинами. Назовем графом ссылок. В контрольном графе не более ребер. Таким образом, каждая MCC (максимально связная компонента) может состоять не более чем из вершин, которых может быть не более . Обратите внимание, что для любой пары графов, имеющих только вершины, мы можем тривиально проверить изоморфизм за полиномиальное время относительноG n f ( n )fGnf(n)O(logn)O(logn)nO(logn)nпотому что мы можем попробовать все перестановки. Таким образом, с помощью жадного алгоритма для присвоения каждому MCC входного графа А MCC в эталонном графике мы можем вычислить обе графы, являются ли isomorph.

Джон Д.
источник
Если я хорошо понял ваше , если число ребер растет только логарифмически по сравнению с то легко отбросить изолированные вершины и проверить за полиномиальное время, является ли изоморфной графу ссылок. Так что для этого ограниченного класса, . fnGΠfP
Марцио Де Биаси
Действительно, это кажется более легким аргументом, чем я думал. Я включу это в свой ответ.
Джон Д.
Учитывая, что та же самая аргументация работает для GI в целом, это не очень удовлетворительно. Я думаю, было бы интересно, если бы можно было улучшить верхнюю границу по краям в настройке , чтобы она больше не отображалась аналогично для работы с GI вообще. Πf
Джон Д.
1
Для аргумента, использующего грубую силу (все перестановки в каждом компоненте), я думаю, что вам действительно нужно, чтобы каждый связанный компонент имел не более вершин:по существу . Однако, используя самый известный алгоритм GI, который занимает время , вы можете заменить на . ( журнал n ) ! ( log n ) log n = n log log n 2 O(logn/loglogn)(logn)!(logn)logn=nloglogn O(logn/loglogn)O(log2n)2vlogvO(logn/loglogn)O(log2n)
Джошуа Грохов