Literatura na temat naiwnego podejścia do izomorfizmu grafów poprzez badanie wielomianów macierzy przylegania

Opisuję podejście do izomorfizmu grafowego, które prawdopodobnie ma fałszywie dodatnie, i jestem ciekawy, czy istnieje literatura wskazująca, że ​​to nie działa.

Biorąc pod uwagę dwa przylegania macierzy , co prawda naiwne Sposób sprawdzania izomorfizmie jest sprawdzenie, czy dla każdego rzędu U z G , znajduje się wiersz V z G , która jest permutacją rzędu u , oznaczony przez G [ u ] ~ H [ v ] . Nieco bardziej rygorystyczne jest pytanie, czy występuje „lokalny izomorfizm” π, dla którego G [ u ] ∼ H [ π ( u ) $G, H$$u$$G$$v$$G$$u$$G[u] \sim H[v]$$\pi$$G[u] \sim H[\pi(u)]$dla wszystkich wierszy. Wytwarzanie lokalnego izomorfizmu można przeprowadzić w czasie wielomianowym, budując macierz A z A [ u , v ] = ( G [ u ] ∼ H [ v ] ) ; wówczas G i H są lokalnie izomorficzne iff A ma pokrycie cyklu, a każde pokrycie cyklu jest lokalnym izomorfizmem.$n\times n$$A$$A[u,v] = (G[u]\sim H[v])$$G$$H$$A$

Wszystkie zwykłe wykresy oszukują tę metodę, więc nieco mniej naiwne podejście polega na obliczeniu mocy macierzy i sprawdzeniu ich pod kątem lokalnego izomorfizmu, wykorzystując fakt, że masz wiele macierzy ustawiając A [ u , v ] = 0 , gdy można znaleźć żadnej siły w taki sposób, 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]$i sprawdzanie pokrycia cyklu tylko na końcu. Jeszcze mniej naiwnym podejściem jest znalezienie zestawu wielomianów, a nawet zestawu obwodów arytmetycznych, i ustawienie gdy znajdziemy dowolny wielomian p z p ( G ) [ u ] ≁ p ( H ) [ v ] .$A[u,v]=0$$p$$p(G)[u]\not\sim p(H)[v]$

Wygląda mi to na niezwykle naiwne podejście do izomorfizmu grafów, więc jestem pewien, że ktoś już to zbadał i udowodnił takie twierdzenie, jak:

Thm Dla nieskończenie wielu macierzy nieizomorficznych n × n macierzy G , H i permutacji π takie, że dla każdego wielomianu p , p ( G ) i p ( H ) są lokalnie izomorficzne według tej permutacji: p ( G ) π ∼ p ( H ) .$n$$n\times n$$G, H$$\pi$$p$$p(G)$$p(H)$$p(G)\overset{\pi}{\sim}p(H)$

Pytanie: Czy istnieje takie twierdzenie? Zajrzałem do literatury i nie mogę jej znaleźć.

Jeżeli istnieje ograniczenie na stopni , która jest wielomian n taki sposób, że na każde dwa nonisomorphic matryc lokalny Izomorfizm jest potwierdzona przez obliczenie G 1 , H, 1 , ... , G s O l r ( n ) , H s O l r ( n ) lub jeśli istnieje łatwo obliczalna rodzina wielomianów p 1 , … , p k , z których każda ma długość wielomianową, ale prawdopodobnie stopień wykładniczy, wówczas mamy P$k$$n$$G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$$p_1, \ldots ,p_k$algorytm dla izomorfizmu grafów. Jeśli takie wielomiany (lub obwody arytmetyczne) są łatwe do odgadnięcia, mamy algorytm coRP . Jeśli zawsze istnieje (rodzina) obwodów arytmetycznych do obserwowania nielokalnego izomorfizmu, daje to algorytm coNP .

Zauważ, że możemy uniknąć problemu, że zapisy macierzy dużej mocy rosną zbyt duże, obliczając wielomiany na małych polach, np. Obliczając je modulo małe liczby pierwsze. W algorytmie CoNP , prover może zapewnić te liczby pierwsze.

Tak, istnieje mniej więcej takie twierdzenie. Zasadniczo stwierdza, że ​​k-wymiarowa procedura Weisfeilera-Lehmana obejmuje (tj. Dominuje) wszystkie znane podejścia kombinatoryczne do testowania izomorfizmu grafów. (Jeśli się nie mylę, twoja konkretna propozycja powinna zostać uwzględniona w dwuwymiarowej procedurze Weisfeilera-Lehmana.) Dla każdego ustalonego k istnieje klasa kontrprzykładów w procedurze k-wymiarowej Weisfeilera-Lehmana znanej jako Cai-Fürer Konstrukcja Immermermana.

Najpierw nauczyłem się podstaw procedury Weisfeiler-Lehman i konstrukcji Cai-Fürer-Immmerman od

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

O procedurze Weisfeilera-Lehmana można się dowiedzieć znacznie więcej niż tam opisano, ale przynajmniej obróbka konstrukcji Cai-Fürera-Immmermana jest kompletna i wystarczająca dla twojego celu. „ Procedura Weisfeilera-Lehmana ” Vikramana Arvinda to niedawny krótki esej mający na celu zaproszenie do tematu.

Być może kluczową kwestią do oderwania się od mojej odpowiedzi jest to, że gdybyś znalazł metodę czysto kombinatorycznego testowania izomorfizmu (taką jak ta opisana w pytaniu), która nie jest objęta (tj. Zdominowana) przez k-wymiarową procedurę Weisfeilera-Lehmana, wówczas byłby to przełom sam w sobie, niezależnie od tego, czy metoda byłaby rzeczywiście przydatna.