4
$\begingroup$

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

  1. A "sifting technique" might help !

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

  3. $G_k$ has no disconnected component.

$\endgroup$
  • $\begingroup$ 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.... $\endgroup$ – Dima Pasechnik Mar 7 '16 at 13:10
  • $\begingroup$ @DimaPasechnik , Consider all $H_k$ are ordered. All you have to do is pick a permutation from each $\beta_k$ to construct $P$. $\endgroup$ – Jim Mar 7 '16 at 14:06
  • 1
    $\begingroup$ Migrating on request of OP... $\endgroup$ – Todd Trimble Mar 14 '16 at 16:20
  • 1
    $\begingroup$ @Jim are you talking about this cstheory.stackexchange.com/questions/21962/…? $\endgroup$ – T.... Mar 15 '16 at 22:40
  • $\begingroup$ @Jim I dont know wait for the experts. $\endgroup$ – T.... Mar 15 '16 at 22:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.