Литература о наивном подходе к изоморфизму графа путем проверки полиномов матриц смежности

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

Учитывая две матрицы смежности , по общему признанию наивный метод проверки изоморфизма состоит в проверке, существует ли для каждой строки u группы G строка v группы G, представляющая собой перестановку строки u , обозначаемую G [ u ] ∼ H [ v ] . Чуть более строгим является вопрос, существует ли «локальный изоморфизм» π, для которого G [ u ] ∼ H [ π ( u ) $G, H$$u$$G$$v$$G$$u$$G[u] \sim H[v]$$\pi$$G[u] \sim H[\pi(u)]$для всех рядов. Создание локального изоморфизма можно осуществить за полиномиальное время, построив матрицу A размером с A [ u , v ] = ( G [ u ] ∼ H [ v ] ) ; тогда G и H локально изоморфны тогда и только тогда, когда A имеет покрытие циклов, и каждое покрытие циклов является локальным изоморфизмом.$n\times n$$A$$A[u,v] = (G[u]\sim H[v])$$G$$H$$A$

Все регулярные графы обманывают этот метод, очевидно, поэтому немного менее наивный подход состоит в том, чтобы вычислять степени матриц и проверять их на локальный изоморфизм, используя тот факт, что у вас есть несколько матриц. установив A [ u , v ] = 0, когда вы найдете любую мощность, такую ​​что G k [ u ] ≁ H k [ v $G^2, H^2, G^3, H^3,\ldots$$A[u,v] = 0$$G^k[u]\not\sim H^k[v]$и проверка покрытия цикла только в конце. Еще менее наивный подход состоит в том, чтобы найти набор многочленов, действительно набор арифметических схем, и установить когда мы найдем любой многочлен p с p ( G ) [ u ] ≁ p ( H ) [ V ] .$A[u,v]=0$$p$$p(G)[u]\not\sim p(H)[v]$

Это выглядит как невероятно наивный подход к изоморфизму графа, поэтому я уверен, что кто-то уже исследовал его и доказал теорему, такую ​​как

$n$$n\times n$$G, H$$\pi$$p$$p(G)$$p(H)$$p(G)\overset{\pi}{\sim}p(H)$

Вопрос: есть ли такая теорема? Я посмотрел в литературе и не могу найти его.

$k$$n$$G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$$p_1, \ldots ,p_k$алгоритм изоморфизма графов. Если такие многочлены (или арифметические схемы) легко угадать, то у нас есть алгоритм coRP . Если всегда существует (семейство) арифметических схем, свидетельствующих о нелокальном изоморфизме, то это дает алгоритм coNP .

Обратите внимание, что мы можем избежать проблемы, заключающейся в том, что элементы мощных матриц становятся слишком большими, вычисляя многочлены над небольшими полями, например, вычисляя их по модулю небольших простых чисел. В алгоритме coNP проверяющий может предоставить эти простые числа.

Да, такая теорема есть, более или менее. В основном утверждается, что k-мерная процедура Вейсфейлера-Лемана объединяет (т.е. доминирует) все известные комбинаторные подходы к проверке изоморфизма графов. (Ваше конкретное предложение должно быть включено в 2-мерную процедуру Вайсфейлера-Лемана, если я не ошибаюсь.) Для каждого фиксированного k существует класс контрпримеров к k-мерной процедуре Вейсфейлера-Лемана, известный как Кай-Фюрер -Immmerman строительство.

Сначала я изучил основы процедуры Вайсфейлера-Лемана и конструкции Кая-Фюрера-Имммермана из

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

О процедуре Вайсфейлера-Лемана можно узнать гораздо больше, чем описано в ней, но, по крайней мере, обработка конструкции Цай-Фюрера-Имммермана завершена и достаточна для вашей цели. « Процедура Вейсфейлера-Лемана », автором которой является Викраман Арвинд, является недавним кратким эссе, предназначенным как приглашение к теме.

Возможно, решающим моментом, который стоит увести от моего ответа, является то, что если вы найдете чисто комбинаторный метод тестирования изоморфизма (такой, как описанный в вашем вопросе), который не включается (то есть доминирует) в k-мерную процедуру Вейсфайлера-Лемана, тогда это будет прорыв сам по себе, независимо от того, будет ли метод действительно полезным.