<p>The computational complexity of of finding $P$ is polynomial in $\beta$.  </p>

<p>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 <strong>[1]</strong>. So, we try to construct the generating set of $Aut(H)$ . The technique used in the paper <strong>[2]</strong>  by E. Luks can used here. </p>

<p><strong>Notation:</strong></p>

<p>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}$$</p>

<p>For simplicity, we assume $\beta \leq n^{3}$.</p>

<p><strong>The outline of the algorithm to construct generating set:</strong></p>

<p>At $1^{st}$ iteration -</p>

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

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

<p>Step 2. Construct/find -</p>

<p>$\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) \}$ </p>

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

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

<p>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 <strong>[3]</strong>.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. </p>

<p>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  <strong>[4]</strong>, we find that $|\mathcal{S}_1| \leq log(n!)$ . 
 $\mathcal{S}_1$ is the  generating set  of automorphism of  $H_1 \cup H_2$ .</p>

<p>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!)$ .</p>

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

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

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

<h2>References:</h2>

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

<p>[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.</p>

<p>[3]Hoffmann, Christoph M. ,Group-Theoretic Algorithms and Graph Isomorphism.</p>

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

<hr>

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

CC BY-SA 3.0
2016-05-29T22:38:38.193Z
2016-06-02T20:30:35.353Z
2016-06-02T20:30:35.353Z
Michael
<p>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).</p>

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

<p>$\pi_k$ is a local isomorphism and $P$ is global isomorphism of $G,H$.</p>

<p>$G_k, \forall k$ is not an $Independent$ $ Set$ .</p>

<p>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.</p>

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

<p>Brute force leads to $\beta^x$. </p>

<p><strong>Does there exist  a  $\beta^c$ algorithm where $c$ is a constant?</strong></p>

<p><strong>Edit:</strong>
1. Consider that  all $H_k$ are ordered according to $G_k$.</p>

<ol start="2">
<li><p>A "sifting technique"  might help !</p></li>
<li><p>$G_k$ has the same vertices of $H_k$.</p></li>
<li><p>$G_k$ has no disconnected component.</p></li>
</ol>

CC BY-SA 3.0
2016-03-07T13:10:46.900Z
it is not clear why such a $P$ would exist. Say, if $H_i$ and $G_j$ all are independent sets of the same size, one would need to find an appropriate ordering of $H_i$, leading potentially to considering $x!$ cases....
Dima Pasechnik
CC BY-SA 3.0
2016-03-07T14:06:48.357Z
@DimaPasechnik , Consider  all $H_k$ are ordered. All you have to do is pick a permutation from each $\beta_k$ to construct $P$.
Michael
CC BY-SA 3.0
2016-03-15T22:40:56.567Z
@Jim are you talking about this http://cstheory.stackexchange.com/questions/21962/graph-isomorphism-given-a-partial-isomorphism/21963#21963?
Turbo
CC BY-SA 3.0
2016-03-15T22:51:31.093Z
@Jim I dont know wait for the experts.
Turbo
CC BY-SA 3.0
2016-03-15T22:59:03.350Z
@Jim I don't know Lipton's result very well.
Turbo
CC BY-SA 3.0
2016-03-15T23:01:20.987Z
@Jim Also not all local maps extend to global isomorphism. What certifies that any permutation in any of $\beta_k$ different local maps extend to any global isomorphism at all? And even they all extend to something are any of the direct products compatible with a single global isomorphism?
Turbo
CC BY-SA 3.0
2016-04-01T13:06:18.533Z
Could you clarify what you mean by "($x$ total vertex set)"? Is there a subgraph for each vertex?
Vincent
CC BY-SA 3.0
2016-04-01T13:08:36.253Z
@Vincent , https://i.sstatic.net/r4VRq.jpg . here, $x=4$, $G_1=\{1,2,3\}$, $G_2=\{4,5,6,7,8,9,10,11,12,13\}$, $G_3=\{14,15,18,19,20,21\}$, $G_4=\{16,17,22,23,24,25\}$ but it violates the 4 th rule under **Edit** .  "Is there a subgraph for each vertex?" is not clear to me.
Michael
CC BY-SA 3.0
2016-04-01T13:50:58.570Z
Right, so the meaning of "total x vertex set" is that the union of the vertex sets of the $G_i$ is the total vertex set of $G$, I take it? Also the vertex sets of the $G_i$ are assumed to be disjoint?
Vincent
CC BY-SA 3.0
2016-04-01T13:57:08.437Z
@Vincent   yes and  yes disjoint vertex set, but dont consider trivial case like complete, graph, null graph or something like that.
Michael
<gr.group-theory><graph-theory><ds.algorithms>
Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism
Michael
# Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism

(Asked by: username_0 on 2016-03-06)

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.

**Tags:** gr.group-theory, graph-theory, ds.algorithms

> **Comments:**
> **username_1**: it is not clear why such a $P$ would exist. Say, if $H_i$ and $G_j$ all are independent sets of the same size, one would need to find an appropriate ordering of $H_i$, leading potentially to considering $x!$ cases....  
> **username_0**: @DimaPasechnik , Consider  all $H_k$ are ordered. All you have to do is pick a permutation from each $\beta_k$ to construct $P$.  
> **username_2**: @Jim are you talking about this http://cstheory.stackexchange.com/questions/21962/graph-isomorphism-given-a-partial-isomorphism/21963#21963?  
> **username_2**: @Jim I dont know wait for the experts.  
> **username_2**: @Jim I don't know Lipton's result very well.  
> **username_2**: @Jim Also not all local maps extend to global isomorphism. What certifies that any permutation in any of $\beta_k$ different local maps extend to any global isomorphism at all? And even they all extend to something are any of the direct products compatible with a single global isomorphism?  
> **username_3**: Could you clarify what you mean by "($x$ total vertex set)"? Is there a subgraph for each vertex?  
> **username_0**: @username_3 , https://i.sstatic.net/r4VRq.jpg . here, $x=4$, $G_1=\{1,2,3\}$, $G_2=\{4,5,6,7,8,9,10,11,12,13\}$, $G_3=\{14,15,18,19,20,21\}$, $G_4=\{16,17,22,23,24,25\}$ but it violates the 4 th rule under **Edit** .  "Is there a subgraph for each vertex?" is not clear to me.  
> **username_3**: Right, so the meaning of "total x vertex set" is that the union of the vertex sets of the $G_i$ is the total vertex set of $G$, I take it? Also the vertex sets of the $G_i$ are assumed to be disjoint?  
> **username_0**: @username_3   yes and  yes disjoint vertex set, but dont consider trivial case like complete, graph, null graph or something like that.  

---

## 1 answers

### Answer by username_0 on 2016-05-29. Score: 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.


---

