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)} &amp; R_{(x, x-1)} &amp; R_{(x,x-2)} &amp; \dots &amp; \dots &amp; R_{(x,1)} \\
R_{(x,x-1)^{T}} &amp; H_{(x-1)} &amp; R_{(x-1,x-2)} &amp; \dots &amp; \dots &amp; R_{(x-1,1)} \\ \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \ddots &amp; \vdots \\
R_{(x,1)^{T}} &amp; R_{(x-1,1)^{T}} &amp; R_{(x-2,1)^{T}} &amp; \dots &amp; \dots &amp;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 &amp; R_{k,e} \\ R_{k,e}^{T} &amp; 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:


$\alpha$ is the generating set of autmorphsim group of  $H$.
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.