"Tiny" Graph Isomorphism

Question

While thinking about the complexity of testing isomorphism of asymmetric graphs (see my related question on cstheory), a complementary question came to my mind.

Suppose that we have a polynomial time Turing machine $M$ that on input $1^n$ generates a graph $G_{M,n}$ with $n$ nodes.

We can define the problem $\Pi_M$:

("Tiny" GI): Given a graph $G=(V,E)$, is $G$ isomorphic to $G_{M,|V|}$?

In other words we must compare a given graph with a "reference" graph of the same size generated by a fixed polynomial time Turing machine $M$.

For all polynomial time Turing machines $M$, we have $\Pi_M \in NP$, and for many of them we have $\Pi_M \in P$.
But is it true for all $M$? Is the problem known?

At first glance, I thought that every $\Pi_M$ should be much easier than $GI$, because for every $n$ there is only one "reference" graph of that size and perhaps the symmetries/asymmetries of the graphs generated by $M$ can be exploited and an efficient ad-hoc isomorphism tester can be built ... but it's not true: $M$ can contain some sort of polynomial timed Universal Turing machine that uses the (unary) input $1^n$ to generate completely different (in the structure) reference graphs as $n$ increases.

Answer 1

[This is more of a few extended comments than an answer.]

1) If $GI \notin \mathsf{P}$, then there is no fixed-polynomial bound on the time complexity of all $\Pi_{M}$, even for $M$ that only take time, say, $n^3$: If for all time-$n^3$ $M$, $\Pi_{M} \in \mathsf{DTIME}(n^k)$, then the following is a poly-time algorithm for GI. On input $(G, H)$, construct a Turing machine $M_{G}$ with a clock which ensures that $M_{G}$ never runs for more than $n^3$ steps on inputs of size $n$, and such that $M_{G}(1^{|V(G)|}) = G$, and then solve $\Pi_{M_G}(H)$ in time $O(n^k)$.

2) Since for any $M$, $\Pi_{M}$ is no harder than GI, one might think that the best result along the lines of "$\Pi_M$ seems not to be in $\mathsf{P}$" one could hope for is a GI-completeness result. However, it seems unlikely to me that any one $\Pi_M$ would be GI-complete, for at least the following reasons:

• All the GI completeness results I know of are for rather large classes of graphs, rather than having a single graph of each size. Even if you drop the efficiency requirement entirely, I do not know of any list of graphs $G_1, G_2, \dotsc$ such that $|V(G_n)| = n$ (or even $poly(n)$) such that testing isomorphism to $G_n$ is GI-complete.

• On a related note, most (all?) GI-completeness results are not merely many-one reductions, but have the following form: there is a function $f$ such that given an instance $(G,H)$ of GI, $(f(G), f(H))$ is instance of the other GI-complete problem. (These are just poly-time morphisms of equivalence relations, or what Fortnow and I called "kernel reductions.) We can easily show unconditionally that there is no such reduction from GI to any $\Pi_M$ (even if you modify the definition to allow $M$ to output multiple graphs). Hint: Get a contradiction by showing that any such $f$ must have its image completely contained in $\{G_{M,n}\}_{n \geq 0}$.

3) Even though one could construct $M$ based on a universal TM as suggested in the question, perhaps one can still construct an efficient tester, just not efficiently. That is, maybe for each $M$, $\Pi_{M}$ is in $\mathsf{P/poly}$?

Answer 2

I have no answer to your question but propose to consider a more restricted version of $\Pi_M$ for which we can show that it lies in P.

Let us only consider families of graphs such that the number of edges grows logarithmically. I will formalize this by rephrasing your problem formulation, also to see if I have understood it correctly.

An undirected graph $G$ with $n$ edges can be described by a $\frac{n^2-n}{2}$ long bitstring, simply concatenate the entries of the adjacency matrix of $G$ in the upper triangle. Therefore there are $2^{\frac{n^2-n}{2}}$ possible graphs on $n$ vertices. It follows that any function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $0 \leq f(n) < 2^{\frac{n^2-n}{2}}$ for all $n$ describes a family of graphs. For any efficiently computable such function $f$ we define $\Pi_f$ as $$ G \in \Pi_f \iff G \text{ is isomorph to the graph described by $f(|V(G)|)$} $$

For a natural number $x$ let $b_1(x)$ be the number of 1's in its binary representation. Now, let us only consider $\Pi_f$ for efficiently computable functions $f$ for which it holds that $$ b_1(f(n)) \in \mathcal{O}(\log n) $$ that is families of graphs for which the number of edges grows only logarithmically, as stated above.

We show that $\Pi_f$ for this class of functions is in P.

Let $f$ be such a function and $G$ be an input graph with $n$ vertices. Let us call $f(n)$ the reference graph. There are at most $\mathcal{O}(\log n)$ edges in the reference graph. Thus every MCC(maximally connected component) can consist of at most $\mathcal{O}(\log n)$ vertices of which there can be at most $n$. Note, that for any pair of graphs with only $\mathcal{O}(\log n)$ vertices we can trivially check isomorphism in polynomialy time w.r.t. $n$ because we can try all permutations. Thus using a greedy algorithm to assign each MCC of the input graph a MCC in the reference graph we can figure out whether the both graphs are isomorph.