Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism

Question

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

2. A "sifting technique" might help !

3. $G_k$ has the same vertices of $H_k$.

4. $G_k$ has no disconnected component.

Answer 1

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 & 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$. Similarly, $S_{k,e}$ represents edges between $G_k, G_e$. $$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\ R_{(x,x-1)} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ R_{(x,1)} & R_{(x-1,1)} & R_{(x-2,1)} & \dots & \dots &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| < 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| < 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| >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 & R_{2,3} \\ R_{2,3}^{T} & 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.