Automorphism of a Graph with a given Set of Permutations

Question

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$.

Answer 1

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.