Sifting Technique : Construction of Isomorphism from sets of Local Isomorphism(Graph Isomorphism)

226 Views Asked by At

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,$\forall k \leq x$, 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$.

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.

$\textbf{Claim :}$ Construction of $P$ can be determined in $O((x \times \beta)^c)$ time where $c$ is constant.

Is the claim correct?