NSPACE for checking if two graphs are isomorphic

Question

I was studying nondeterministic Turing Machines and came across the following question:

Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are isomorphic, and provide the NSPACE. The NTM should use as little space as possible.

My attempt at answering this question goes something like this:

• If G1 and G2 have different no. of vertices and/or edges, reject
• Nondeterministically reorder the vertices v1 thru vn in G1. Leave G2 alone.
• Check if there is a bijection from G1 to G2, with the above vertex mapping. If so, accept.

At some point, the above algorithm will go thru all n! possible orderings of G1's vertices, and will exhaustively check to see if there's a bijection.

Not quite sure what the NSPACE() value is, though, or how I would go about computing it. My guess is that re-ordering G1's vertices v1 thru vn will take up n cells of the work tape, and checking every pair of vertices for bijection will require a small additional amount of space that can be reused for each subsequent pair? Or do we actually need to store all C(n, 2) pairs per graph?

This is all very confusing, and I'm unsure whether I'm thinking thru this problem the right way. I'd appreciate any help.

Answer 1

Saying that at some point your algorithm goes through all $n!$ options is incorrect. You "guess" the permutation, and then check if it is an isomorphism, not just a bijection, the important condition you need to verify is $(u,v)\in E_{G_1} \iff \left(f(u), f(v)\right)\in E_{G_2}$. You need to store the permutation (which requires $n\log n$ space, since keeping the index of a vertex in {v_1,...,v_n} requires $\log n $ space). The verfication can reuse space, so you only need enough additonal space to find the permutations $f(u), f(v)$ for any edge $(u, v) \in E_{G_1}$, and check if the corresponding edge exists in $G_2$. To find those you only need counters up to $n$, which can be saved in logarithmic space. Overall you used $O(n\log n)$ space. Note that you didn't actually need the power of PSPACE here (didn't do anything exponential), so this also proves $GI\in NTIME(n\log n)$.

Answer 2

The algorithm you proposed can be made to work in $O(n \log n)$-space, where $n$ is number of vertices. While permuting the vertices of graph $G_1$, you can also keep the mapping and reverse mapping from and to original vertices. That way you need not rewrite the whole graph. And you can still check if a particular edge in $G_1$ maps to an edge in $G_2$ and vice-versa.

Also, planar graph isomorphism is log-space.