# Automorphism of a Graph with a given Set of Permutations

Given a graph $H$. A set of permutations $\alpha$ which contains permutations of vertices of $H$.

The permutation set $\alpha$ has automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the number of total subgraphs. These subgraphs are connected. These permutations can be extended to the automorphism of $H$. By extending, we mean that automorphism of subgraphs can be extended to the automorphism of graph $H$. This concept is similar to E. Luks' paper of graph siomorphism of bounded valence.

Each subgraph has constant number of vertices. The adjacency matrix of $H$ is -

$$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\ R_{(x,x-1)^{T}} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ R_{(x,1)^{T}} & R_{(x-1,1)^{T}} & R_{(x-2,1)^{T}} & \dots & \dots &H_{1} \end{bmatrix}$$

The adjacency matrix of graph $H_k \cup H_e$ is $M_{(k,e)}$ where $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right)$, where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$. Here, $R_{k,e}$ represents edges between $H_k, H_e$.

Problem: How to find an automorphism of $H$ in polynomial time (in $\alpha$)?

Note:

1. $\alpha$ is the generating set of autmorphsim group of $H$.
• $R_{k,e}$ is set of edges between subgraph $H_k$ and subgraph $H_{e}$ ? – Michael Jun 6 '16 at 4:11
• I don't understand the problem statement. $\alpha$ is a set, right? What is each element? Is it a permutation of vertices of $H$? Is it an automorphism of some $H_i$? What does it mean "these permutations can be extended to the automorphism of $H$"? How does $H$ relate to $H_1,\dots,H_x$? Are they a disjoint partition of the vertices of $H$? Is this a directed graph or an undirected graph? What makes you think it's possible to build an automorphism of $H$ in polynomial time? I presume you want a non-trivial automorphism? What approaches have you tried? – D.W. Jun 6 '16 at 4:40
• @D.W. , we can start with $H_1$ and $H_2$ and see direct products of $\alpha$ creates an automorphism of graph $H_1 \cap H_2$ . Since it is given, that permutations of $\alpha$ extend to an automorphism of $H$, so, I will find an automorphism, and recurse the process, until I find the auto of $H$ – Michael Jun 6 '16 at 4:47
• 1. "I don't understand the problem statement. α is a set, right? What is each element? " Is it a permutation of vertices of H? Is it an automorphism of some Hi?- yes to all. 2. What does it mean "these permutations can be extended to the automorphism of H"? -- this is term you use when you find auto: from subgraphhs and extend it to whole graph 3. Are they a disjoint partition of the vertices of H? ----yes 4. Is this a directed graph or an undirected graph? --- unirected. @D.W. – Michael Jun 6 '16 at 4:51
• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Jun 6 '16 at 9:02

If you only want an automorphism, then just consider the identity permutation. That's an automorphism -- the trivial automorphism.

If you want a non-trivial automorphism, then if I understand your problem statement, this is as hard as the graph automorphism problem. No polynomial-time algorithm is known for this problem. It's not known to be NP-complete (it's not even known to be GI-complete). Nonetheless, finding a polynomial-time algorithm for this problem is an open problem, so you shouldn't expect it to be easy to find a polynomial-time algorithm for your problem, either.

In practice you can use open-source tools like Nauty, BLISS, or SAUCY to find an automorphism; on most graphs they (empirically) are very fast.

Justification of claim that this is as hard as graph automorphism:

We can reduce graph automorphism to your problem. Let $G$ be an arbitrary undirected graph, with $n$ vertices. Construct an undirected graph $H$ with $2n$ vertices as follows: for each vertex $v$ of $G$, add another vertex $v'$, and add an edge $(v,v')$. Keep all the edges between unprimed vertices, but don't add any edges between primed vertices.

Note that the automorphisms of $G$ are in one-to-one correspondence with the automorphisms of $H$. If $\pi$ is an automorphism of $G$, it can be extended to an automorphism of $H$ simply by permuting the primed vertices in the same way as the unprimed vertices. If $\pi'$ is an automorphism of $H$, by projecting it to the vertex set of $G$ we obtain an automorphism of $G$.

Now define $H_1,\dots,H_n$ as follows: each $H_i$ is the subgraph induced by the two vertices $v_i,v'_i$. In other words, $H_i$ has vertex set $\{v_i,v'_i\}$ and has a single edge $(v_i,v'_i)$. Thus, $H_i$ has a non-trivial automorphism that swaps $v_i$ and $v'_i$, and this corresponds to a permutation $\pi_i$ of $H$ (one that leaves all other vertices of $H$ fixed). Define $\alpha$ to be this set of permutations.

Now if you can find a non-trivial automorphism of $H$, you can immediately obtain a non-trivial automorphism of $G$ (i.e., you've found a way to solve the graph automorphism problem on an arbitrary graph $G$). If $H$ has no non-trivial automorphism, neither does $G$. This completes the reduction.