Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
An other interesting exercise: find a NTM that given a graph $G$ and two nodes $v_1$ and $v_2$ returns true if there is a path from $v_1$ to $v_2$, false otherwise. Use $O(\log n)$ space. – Bakuriu Feb 29 at 14:09
up vote 2 down vote accepted

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)$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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