Literatur über einen naiven Ansatz zum Graphisomorphismus durch Untersuchung von Polynomen von Adjazenzmatrizen

Ich beschreibe einen Ansatz zum Graphisomorphismus, der wahrscheinlich falsch positiv ist, und ich bin gespannt, ob es Literatur gibt, die darauf hinweist, dass er nicht funktioniert.

Bei zwei Adjazenzmatrizen besteht eine zugegebenermaßen naive Methode zur Überprüfung auf Isomorphismus darin, zu prüfen, ob es für jede Zeile u von G eine Zeile v von G gibt, die eine Permutation der Zeile u ist , die mit G [ u ] ∼ H bezeichnet wird [ v ] . Etwas strenger ist die Frage, ob es einen "lokalen Isomorphismus" π gibt, für den G [ u ] ∼ H [ π ( u ) $G, H$$u$$G$$v$$G$$u$$G[u] \sim H[v]$$\pi$$G[u] \sim H[\pi(u)]$für alle Zeilen. Die Erzeugung eines lokalen Isomorphismus kann in Polynomzeit erfolgen, indem eine Matrix A mit A [ u , v ] = ( G [ u ] ∼ H [ v ] ) erstellt wird ; dann sind G und H lokal isomorph, wenn A eine Zyklusabdeckung hat und jede Zyklusabdeckung ein lokaler Isomorphismus ist.$n\times n$$A$$A[u,v] = (G[u]\sim H[v])$$G$$H$$A$

Alle regulären Graphen täuschen diese Methode offensichtlich vor, daher besteht ein etwas weniger naiver Ansatz darin, die Potenzen der Matrizen zu berechnen und sie auf lokalen Isomorphismus zu überprüfen, wobei die Tatsache ausgenutzt wird, dass Sie mehrere Matrizen haben indem Sie A [ u , v ] = 0 setzen, wenn Sie eine Potenz finden, so dass 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]$und erst am Ende auf Fahrradabdeckung prüfen. Ein noch weniger naiver Ansatz besteht darin, eine Menge von Polynomen zu finden, tatsächlich eine Menge von arithmetischen Schaltkreisen, und wenn wir ein Polynom p mit p ( G ) [ u ] ≁ p ( H ) [finden v ] .$A[u,v]=0$$p$$p(G)[u]\not\sim p(H)[v]$

Dies scheint mir ein unglaublich naiver Ansatz für den Graphisomorphismus zu sein, daher bin ich sicher, dass jemand ihn bereits untersucht und einen Satz wie bewiesen hat

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

Frage: Gibt es einen solchen Satz? Ich habe in der Literatur gesucht und kann sie nicht finden.

$k$$n$$G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$$p_1, \ldots ,p_k$Algorithmus für den Graphisomorphismus. Wenn solche Polynome (oder arithmetische Schaltungen) leicht zu erraten sind, haben wir einen coRP- Algorithmus. Wenn es immer eine (Familie von) arithmetischen Schaltungen gibt, die einen nicht lokalen Isomorphismus beobachten, ergibt dies einen coNP- Algorithmus.

Beachten Sie, dass wir das Problem vermeiden können, dass die Einträge von Hochleistungsmatrizen zu groß werden, indem wir die Polynome über kleinen Feldern berechnen, z. B. indem wir sie modulo kleinen Primzahlen berechnen. In einem coNP- Algorithmus kann der Prüfer diese Primzahlen bereitstellen.

Ja, es gibt mehr oder weniger einen solchen Satz. Grundsätzlich heißt es, dass das k-dimensionale Weisfeiler-Lehman-Verfahren alle bekannten kombinatorischen Ansätze zur Prüfung des Graphisomorphismus subsumiert (dh dominiert). (Ihr konkreter Vorschlag sollte nach dem zweidimensionalen Weisfeiler-Lehman-Verfahren zusammengefasst werden, wenn ich mich nicht irre.) Für jedes feste k gibt es eine Klasse von Gegenbeispielen zum k-dimensionalen Weisfeiler-Lehman-Verfahren, das als Cai-Fürer bekannt ist -Immmerman Konstruktion.

Ich habe zuerst die Grundlagen des Weisfeiler-Lehman-Verfahrens und der Cai-Fürer-Immmerman-Konstruktion von gelernt

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

Über das Weisfeiler-Lehman-Verfahren gibt es viel mehr zu lernen als dort beschrieben, aber zumindest die Behandlung der Cai-Fürer-Immmerman-Konstruktion ist vollständig und für Ihren Zweck ausreichend. " Das Weisfeiler-Lehman-Verfahren " von Vikraman Arvind ist ein kürzlich veröffentlichter kurzer Aufsatz, der als Einladung zum Thema gedacht ist.

Vielleicht ist der entscheidende Punkt, der meiner Antwort entzogen werden sollte, dass, wenn Sie eine rein kombinatorische Isomorphismus-Testmethode finden würden (wie die in Ihrer Frage beschriebene), die nicht durch das k-dimensionale Weisfeiler-Lehman-Verfahren subsumiert (dh dominiert) wird, dann wäre dies ein Durchbruch für sich, unabhängig davon, ob die Methode tatsächlich nützlich wäre.