10
$\begingroup$

I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work.

Given two adjacency matrices $G, H$, an admittedly naive method of checking for isomorphism is to check whether for each row $u$ of $G$, there is a row $v$ of $G$ which is a permutation of row $u$, denoted by $G[u] \sim H[v]$. Slightly more strict is the question, is there a "local isomorphism" $\pi$ for which $G[u] \sim H[\pi(u)]$ for all rows. Producing a local isomorphism can be done in polynomial time by building an $n\times n$ matrix $A$ with $A[u,v] = (G[u]\sim H[v])$; then $G$ and $H$ are locally isomorphic iff $A$ has a cycle cover, and every cycle cover is a local isomorphism.

All regular graphs fool this method, obviously, so a slightly less naive approach is to compute powers $G^2, H^2, G^3, H^3,\ldots$ of the matrices and checking them for local isomorphism, exploiting the fact that you have multiple matrices by setting $A[u,v] = 0$ when you find any power such that $G^k[u]\not\sim H^k[v]$, and checking for cycle cover only at the end. An even less naive approach is to find a set of polynomials, indeed a set of arithmetic circuits, and setting $A[u,v]=0$ when we find any polynomial $p$ with $p(G)[u]\not\sim p(H)[v]$.

This looks to me like an incredibly naive approach to graph isomorphism, so I am sure somebody has already investigated it and proved a theorem such as

Thm For infinitely many $n$ there are nonisomorphic $n\times n$ matrices $G, H$ and a permutation $\pi$ such that for every polynomial $p$, $p(G)$ and $p(H)$ are locally isomorphic by that permutation: $p(G)\overset{\pi}{\sim}p(H)$.

Question: Is there such a theorem? I have looked in the literature and cannot find it.

If there is a bound on the degree $k$ that is polynomial in $n$ such that for every two nonisomorphic matrices, local isomorphism is refuted by computing $G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$, or if there is an easily computable family of polynomials $p_1, \ldots ,p_k$, each having polynomially-bounded length but possibly exponential degree, then we have a P algorithm for graph isomorphism. If such polynomials (or arithmetic circuits) are easy to guess, then we have a coRP algorithm. If there always exists a (family of) arithmetic circuits to witness non local isomorphism, then this gives a coNP algorithm.

Note that we can avoid the problem that the entries of high-power matrices grow too large by computing the polynomials over small fields, e.g. by computing them modulo small primes. In a coNP algorithm, the prover can provide these primes.

$\endgroup$
11
$\begingroup$

Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism testing. (Your concrete proposal should be subsumed by the 2-dimensional Weisfeiler-Lehman procedure, if I am not mistaken.) For each fixed k, there is a class of counterexamples to the k-dimensional Weisfeiler-Lehman procedure known as the Cai-Fürer-Immmerman construction.

I first learned the basics of the Weisfeiler-Lehman procedure and the Cai-Fürer-Immmerman construction from

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

There is much more to learn about the Weisfeiler-Lehman procedure than described there, but at least the treatment of the Cai-Fürer-Immmerman construction is complete and sufficient for your purpose. "The Weisfeiler-Lehman Procedure", by Vikraman Arvind is a recent brief essay meant as an invitation to the topic.

Perhaps the crucial point to take away from my answer is that if you would find a purely combinatorial isomorphism testing method (like the one describe in your question), which is not subsumed (i.e. dominated) by the k-dimensional Weisfeiler-Lehman procedure, then this would be a breakthrough by itself, independent of whether the method would be actually useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.