# “Tiny” Graph Isomorphism

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.

• Interesting, Do you know an example P-time Turing machine $M$ that generates graph $G_{M,N}$? – Mohammad Al-Turkistany Jun 7 '14 at 18:42
• @MohammadAl-Turkistany: A trivial example for which $\Pi_M \in P$, is a TM $M$ that simply outputs $n$ isolated vertices (or another one is a TM that outputs $K_n$). Without loss of generality we can also think of a model in which every polynomial time TM over binary alphabet generates a reference graph: just pick the first $n^2$ bits of the tape after it halts, and interpret it as the adjacency matrix of $G_{M,n}$. – Marzio De Biasi Jun 8 '14 at 0:02
• For TM $M$ that guarantees that $G_{M,n}$ has Hamiltonian cycle, then I guess $\Pi_M$ is not in $P$. – Mohammad Al-Turkistany Jun 8 '14 at 22:38
• @MohammadAl-Turkistany: I think it's not true: just pick a TM that simply builds a cycle of $n$ nodes: for all $n$ the reference graph - that has an Hamiltonian cycle - is easily checkable in polynomial time. I have in mind a non-trivial example of a (rather simple) generator for which it seems hard to show that the problem is in $P$; but I want to do some tests with nauty before adding it to the question. – Marzio De Biasi Jun 8 '14 at 23:31
• What about the "Itsy Bitsy" GI where for a fixed M and N we have to decide if the two graphs generated on 1^n are the same? (This is a unary language.) – domotorp Jun 10 '14 at 12:19

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}$?

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.

• If I understood well your $f$, if the number of edges grows only logarithmically w.r.t. $n$ then it is easy to drop away the isolated vertices and test in polynomial time if $G$ is isomorphic to the reference graph. So for this restricted class, $\Pi_{f} \in P$. – Marzio De Biasi Jun 7 '14 at 9:57
• Indeed, it seems to be an easier argument than I thought. I will incorporate it in my answer. – John D. Jun 7 '14 at 10:04
• Considering that the same argumentation works for GI in general this isn't really satisfying. I guess it would be interesting if one could improve the upper bound on the edges in the $\Pi_f$ setting such that it can't be shown analogously to work for GI in general anymore. – John D. Jun 7 '14 at 10:53
• For the argument using brute force (all permutations in each component), I think you actually need each connected component to have at most $O(\log n / \log \log n)$ vertices: $(\log n)!$ is essentially $(\log n)^{\log n} = n^{\log \log n}$. However, using the best known GI algorithm which takes time $2^{\sqrt{v \log v}}$, you can replace $O(\log n/\log \log n)$ by $O(\log^2 n)$. – Joshua Grochow Jun 9 '14 at 3:23