How string isomorphism is used in graph isomorphism?

744 Views Asked by At

Graph isomorphism is a special case of string isomorphism problem. In the paper of Graph Isomorphism in Quasipolynomial Time, the relation has been shown. Let, two strings $x,y$ are associated with graphs $A, B$ (each has $n$ vertices) respectively. If there exists a permutation $\pi \in S_n$ (symmetric group of $n$ vertices), so that $x^{\pi}=y$, it implies that $A^{\pi}=B$, i.e. graphs $A, B$ are isomorphic.

In the paper, the definition of string isomorphism is written on page 24 - $\newcommand{\Iso}{\operatorname{Iso}}\newcommand{\Aut}{\operatorname{Aut}}$

Definition 3.2 (String Isomorphism Problem).

Input: a set $\Omega$, a finite alphabet $\Sigma$, two strings $x, y :\Omega → \Sigma,$ a permutation group $G ≤ S(Ω)$ (given by a list of generators)

Output: The set $\Iso_G(x, y)$. If this set is nonempty, it is represented by a list of generators of the group $\Aut_G(x)$ and a coset representative $\sigma \in \Iso_G(x, y)$.

here, $G$ is an arbitrary sub-group of $S(Ω)$ (see [this][2]). What happens if $\Iso_G(x, y)$ is empty?

If $\Iso_G(x, y)$ is empty, then there might be $H > G$ where $\pi \in H$ and $\pi$ is an isomorphism. So, $\Iso_G(x, y) = \emptyset$ does not imply $A, B$ are not isomorphic. In this case, what is the next step?

In general, why an arbitrary group $G$ is enough to check graph isomorphism?

1

There are 1 best solutions below

7
On

It sounds like you're somehow confused about which way the reduction goes and/or who gets choose $G$.

Someone who claims they have a solution to your "string isomorphism problem" must be able to handle every possible subgroup we throw at them. That's what it means to say that the group is arbitrary.

In particular if you're trying to solve the usual graph-isomorphism problem with the help of a string-isomorphism solver, having freedom to choose a group yourself makes your job easier. It means that you can construct a subgroup to represent exactly all of the possible permutation of the vertices in your graph, and then the string-isomorphism solver has to work with the group you constructed.

The group $G$ is part of the input to the string-isomorphism problem. Having a wide variety of possible inputs makes it (potentially) more difficult to find a general solution to the problem, but on the other hand makes it easier to use a solver as a tool for solving other problems.

So asking "why is an arbitrary group enough to check graph isomorphism" is fundamentally misunderstood. The more groups you have to choose between, the better the chance that the one you need in order to check a graph isomorphism. And when you get a free choice between all of them, as you do here, you can be sure that the group you need will be supported.