3
$\begingroup$

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem-

Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time algorithm for Graph − Aut (automorphism) and vice-versa.

on page 2, the proof is given-

Proof. First we shall show that we can solve Graph−Iso with Graph−Aut as an oracle. We are given two graphs $G_1$ and $G_2$ and we need to create a graph G using the two such that the generating set of the automorphism should tell us if they are isomorphic or not. Let $G = G_1 \cup G_2$. Suppose additionally we knew that $G_1$ and $G_2$ are connected, then a single oracle query would be sufficient. If any of the generators of $Aut(G)$ interchanged a vertex in $G_1$ with one in $G_2$, then connnectivity should force $G_1 \simeq G_2$. But what if they are not connected? We then have this very neat trick, $G_1 \simeq G_2 \Leftrightarrow \bar G_1\simeq \bar G_2$ , and either $G_1$ or $\bar G_1$ has to be connected and hence one can check for connectivity and then ask the appropriate query.

$\bar G_1$ is the complement graph of $G_1$, I assume.

It is said that-

Suppose additionally we knew that $G_1$ and $G_2$ are connected, then a single oracle query would be sufficient.

But when we test graph isomorphism, $G_1 , G_2$ are two different disconnected graph. Is it why it went on like-

But what if they are not connected? We then have this very neat trick, $G_1 \simeq G_2 \Leftrightarrow \bar G_1\simeq \bar G_2$, and either $G_1$ or $\bar G_1$ has to be connected and hence one can check for connectivity and then ask the appropriate query.

So, are we checking whether there is an automorphism of $G' = \bar G_1 \cup \bar G_2$ that swaps a vertex of $\bar G_1$ with a vertex of $\bar G_2$?

How can we tell that this kind of swapping is an automorphism?

$\endgroup$
  • $\begingroup$ Example: $r$ is a permutation that swaps only 2 vertices of $ G_1$ . Let, $G_1^{r} = G_2$. Let, $G= G_1 \cup G_2$. Clearly, $G$ is a disconnected graph, so we try $G' = \bar G_1 \cup \bar G_2$ instead of $G$. But how we detect an automorphism of $G'$ ? $\endgroup$ – Michael May 23 '16 at 20:29
4
$\begingroup$

Yes, you are checking whether there is an automorphism of $G^{\prime} = \bar{G}_{1} \cup \bar{G}_{2}$ that swaps a vertex of $\bar{G}_{1}$ with a vertex of $\bar{G}_{2}$. You are using Graph-Aut as an oracle, so what you will do is use Graph-Aut to find the automorphism group of $G^{\prime}$ (returned as a set of generators), then just look at whether any of these generators swap vertices of $G_{1}$ with those of $G_{2}$. You don't need to do anything to tell if this swapping is an automorphism, it is automatically an automorphism because it's returned by Graph-Aut.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ probably I am making a mistake here, does $G_1 \cup G_2$ has any edge between $G_1 , G_2$ ? similarly, does $\bar G_1 \cup \bar G_2$ has any has any edge between $\bar G_1 , \bar G_2$ ? $\endgroup$ – Michael May 24 '16 at 13:56
  • 1
    $\begingroup$ @Jim No, $G_{1} \cup G_{2}$ is a disjoint union, so there are no edges between $G_{1}$ and $G_{2}$ (you want $G_{1}$ and $G_{2}$ to each be connected, but $G = G_{1} \cup G_{2}$ will be disconnected, with $G_{1}$ and $G_{2}$ being the connected components). $\endgroup$ – Morgan Rodgers May 24 '16 at 20:03

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.