<p>[This is more of a few extended comments than an answer.]</p>

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

<p>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: </p>

<ul>
<li><p>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.</p></li>
<li><p>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 <a href="http://arxiv.org/abs/0907.4775">Fortnow and I</a> 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}$.</p></li>
</ul>

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

CC BY-SA 3.0
2014-06-09T05:06:38.287Z
2014-06-09T05:06:38.287Z
Joshua Grochow
<p>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.</p>

<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.</p>

<p>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) &lt; 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)|)$} $$</p>

<p>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.</p>

<p>We show that $\Pi_f$ for this class of functions is in P.</p>

<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.  </p>

CC BY-SA 3.0
2014-06-07T09:57:22.993Z
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
CC BY-SA 3.0
2014-06-07T10:04:55.067Z
Indeed, it seems to be an easier argument than I thought. I will incorporate it in my answer.
John D.
CC BY-SA 3.0
2014-06-07T10:53:42.717Z
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.
CC BY-SA 3.0
2014-06-09T03:23:11.537Z
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
CC BY-SA 3.0
2014-06-07T09:34:10.620Z
2014-06-07T10:20:00.010Z
2014-06-07T10:20:00.010Z
John D.
<p>While thinking about the complexity of testing isomorphism of asymmetric graphs (see my <a href="https://cstheory.stackexchange.com/questions/22094/testing-isomorphism-of-asymmetric-graphs">related question</a> on cstheory), a complementary question came to my mind.</p>

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

<p>We can define the problem $\Pi_M$:</p>

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

<p>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$.</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-06-07T18:42:54.210Z
Interesting, Do you know an example P-time Turing machine $M$ that generates graph $G_{M,N}$?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-06-08T00:02:48.910Z
@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
CC BY-SA 3.0
2014-06-08T22:38:04.583Z
For TM $M$ that guarantees that $G_{M,n}$ has Hamiltonian cycle, then I guess $\Pi_M$ is not in $P$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-06-08T23:31:32.530Z
@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
CC BY-SA 3.0
2014-06-08T23:50:24.630Z
How about if $G_{M,n}$ is cubic Hamiltonian graph?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-06-10T12:19:37.807Z
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
CC BY-SA 3.0
2014-06-10T13:09:19.943Z
@domotorp: another beast! :-) ... I thought about it in this version: on input $1^{n^2}$ check if $M_1$,$M_2$ (fixed) produce the same matrix $A$ up to column/row permutations.
Marzio De Biasi
<graph-isomorphism>
"Tiny" Graph Isomorphism
Marzio De Biasi
# "Tiny" Graph Isomorphism

(Asked by: username_0 on 2014-06-06)

While thinking about the complexity of testing isomorphism of asymmetric graphs (see my [related question](https://cstheory.stackexchange.com/questions/22094/testing-isomorphism-of-asymmetric-graphs) 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.

**Tags:** graph-isomorphism
> **Comments:**
> **username_1**: Interesting, Do you know an example P-time Turing machine $M$ that generates graph $G_{M,N}$?  
> **username_0**: @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}$.  
> **username_1**: For TM $M$ that guarantees that $G_{M,n}$ has Hamiltonian cycle, then I guess $\Pi_M$ is not in $P$.  
> **username_0**: @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.  
> **username_1**: How about if $G_{M,n}$ is cubic Hamiltonian graph?  
> **username_2**: 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.)  
> **username_0**: @domotorp: another beast! :-) ... I thought about it in this version: on input $1^{n^2}$ check if $M_1$,$M_2$ (fixed) produce the same matrix $A$ up to column/row permutations.  

---

## 2 answers

### Answer by username_3 on 2014-06-09. Score: 6

[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](http://arxiv.org/abs/0907.4775) 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 by username_4 on 2014-06-07. Score: 1

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.

> **Comments:**
> **username_0**: 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$.  
> **username_4**: Indeed, it seems to be an easier argument than I thought. I will incorporate it in my answer.  
> **username_4**: 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.  
> **username_3**: 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)$.  

---

