19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting, Do you know an example P-time Turing machine $M$ that generates graph $G_{M,N}$? $\endgroup$ – Mohammad Al-Turkistany Jun 7 '14 at 18:42
  • $\begingroup$ @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}$. $\endgroup$ – Marzio De Biasi Jun 8 '14 at 0:02
  • $\begingroup$ For TM $M$ that guarantees that $G_{M,n}$ has Hamiltonian cycle, then I guess $\Pi_M$ is not in $P$. $\endgroup$ – Mohammad Al-Turkistany Jun 8 '14 at 22:38
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Jun 8 '14 at 23:31
  • 1
    $\begingroup$ 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.) $\endgroup$ – domotorp Jun 10 '14 at 12:19
6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Marzio De Biasi Jun 7 '14 at 9:57
  • $\begingroup$ Indeed, it seems to be an easier argument than I thought. I will incorporate it in my answer. $\endgroup$ – John D. Jun 7 '14 at 10:04
  • $\begingroup$ 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. $\endgroup$ – John D. Jun 7 '14 at 10:53
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Joshua Grochow Jun 9 '14 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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