Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume  $H$ has  subgraphs $H_1, H_2... H_x$ (total $x$ vertex set).

Consider, a permutation $\pi_k \in \beta_k$ where $H_k^{\pi_k}=G_k$ such that $P= \pi_1 \times \pi_2...\pi_x$ (i.e. $P$ is  the direct product of permutations $\pi_1, \pi_2 ..... \pi_x$) and $H^P=G$.

$\pi_k$ is a local isomorphism and $P$ is global isomorphism of $G,H$.

$G_k, \forall k$ is not an $Independent$ $ Set$ .

Here, $\beta_k (k\leq x \leq n/2)$ is a set of permutations  for each $H_k$. Let, $\beta$ is a number and $\beta_k$ has maximum $\beta$ permutations.

Question  If All $\beta_k$ are given, how many steps are required to construct $P$, i.e. what is the computational complexity of finding $P$?

Brute force leads to $\beta^x$. 

Does there exist  a  $\beta^c$ algorithm where $c$ is a constant?

Edit:
1. Consider that  all $H_k$ are ordered according to $G_k$.


A "sifting technique"  might help !
$G_k$ has the same vertices of $H_k$.
$G_k$ has no disconnected component.
The computational complexity of of finding $P$ is polynomial in $\beta$.  

We construct the generating set of automorphism group of $H$ using  $\beta_k$, for all $k$. As we know, constructing  generating set of automorphism group of  $H$ is a  GI complete problem [1]. So, we try to construct the generating set of $Aut(H)$ . The technique used in the paper [2]  by E. Luks can used here. 

Notation:

From now on, $G, H$ are adjacency matrices of graphs $G, H$ respectively. $H_k, G_k$ are blocks or sub-matrices of matrix $H, G$ respectively. 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$.  Similarly,  $S_{k,e}$ represents  edges  between $G_k, G_e$.
$$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)} &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)} &amp; R_{(x-1,1)} &amp; R_{(x-2,1)} &amp; \dots &amp; \dots &amp;H_{1} \end{bmatrix}$$

For simplicity, we assume $\beta \leq n^{3}$.

The outline of the algorithm to construct generating set:

At $1^{st}$ iteration -

Step 1. Construct all possible  direct product  $(\pi_1 \times  \pi_2)$ where $\pi_1 \in \beta_1$ and $ \pi_2 \in \beta_2$. 

There are $| \beta_1 | \times | \beta_2|  &lt;  n^{9}$ direct products (permutations).  All these permutations (direct products) form set $\gamma_1$. Each element of $\gamma_1$ is a permutation that acts on graph $H_1 \cup  H_2$.

Step 2. Construct/find -

$\alpha_1 =\{ \pi \in \gamma_1 |  (M_{(1,2)}^{\pi}= M_{(1,2)}) \land ( R_{1,2}^{\pi} = S_{1,2}) \land  (H_1^{\pi} = G_1) \land  (H_2^{\pi} = G_2) \}$ 

$\alpha_1$ is the set of automorphisms of matrix $M_{(1,2)}$.        $|\alpha_1| &lt; n^{9}$.There are two possible cases-

Case 1:  If $|\alpha_1| =1$, then  for each $\pi_1 \in \beta_1$,  there is only one permutation
$\pi_2 \in \beta_2$. So, there could be maximum $n^{2}$ permutations in $\gamma_1$ but only one permutation could be included in $\alpha_1$.

Case 2: If $|\alpha_1| &gt;1$,  we would be able to construct a generating set $\mathcal{S}_1$ of an automorphism group of $Aut(M_{(1,2)})$ Note, that if $\exists \pi_a \in Aut(H)$ such that it acts on   vertices of $H_1 \cup H_2$, then  $  \pi_a \in \langle \mathcal{S}_1 \rangle =Aut(M_{(1,2)})$. So, when we construct direct product of  $\mathcal{S}_1$ and another set,   $\pi_a$ can be found in the resulting generating set. See Theorem 7, on page 31 of [3].The theorem showed how to obtain the automorphism group of an arbitrary graph from the intersection of a specific  permutation group with a direct product of symmetric groups. 

Step 3. Now, we construct the generating set  $\mathcal{S}_1$  from $\alpha_1$. This construction of generating set can be done in polynomial time (see [3], page 40, theorem 9). From  [4], we find that $|\mathcal{S}_1| \leq log(n!)$ . 
 $\mathcal{S}_1$ is the  generating set  of automorphism of  $H_1 \cup H_2$ .

Step 4. We start $2^{nd}$ iteration, for $\beta_3, \mathcal{S}_1$ (instead of $\beta_2$), $ M_{(2,3)}$  where $M_{(2,3)} =\left( \begin{array}{ccc} H_3 &amp; R_{2,3} \\ R_{2,3}^{T} &amp; H_2 \\ \end{array} \right) $.  We find $\gamma_2, \alpha_2$ repeating  steps $1,2$ and construct $\mathcal{S}_2$ (repeating  step $3$)  which  is the  generating set  of automorphism of  graph $H_1 \cup H_2 \cup H_3$. Note that,                    $|\mathcal{S}_2|  \leq log(n!)$ .

Step  5. We keep repeating above  four   processes, until we find the set $\mathcal{S}_{(x-1)} $  which  is the  generating set  of automorphism of graph $H_1 \cup H_2 \cup H_3 \dots \cup H_x=H $. Note that, $|\mathcal{S}_{(x-1)}|\leq  log(n!)$, since $ \langle \mathcal{S}_{(x-1)} \rangle= Aut(H) \leq S_n$. 

Detecting Isomorphism:  We repeat the process of construction of $\mathcal{S}_{(x-1)}$ for graph $G$ and obtain set $\mathcal{R}_{(x-1)}$. I assumed, that  the oracle that gave $\beta_k$, would provide permutation sets for $G$ also.

Once we generate  generating sets of $G, H$, we can decide isomorphism betwen them [1].

References:

[1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132. 

[2] Luks , Eugene M. , Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Volume 25, Issue 1, (1982), Pages 42-65.

[3]Hoffmann, Christoph M. ,Group-Theoretic Algorithms and Graph Isomorphism.

[4] Miller, Gary L.  ,On the $n^{\log_2(n)}$ Isomorphism Technique.



Feel free to down-vote, but please leave a comment if you have anything  technical to say, Thanks for your patience.