Suppose, I have a fixed number of permutations for each sub-graph to determine isomorphism of whole graph. Is it possible to determine efficiently ?
For example, $G, H$ are isomorphic graphs. For subgraphs $G_1, G_2, G_3$ of graph $G$ there are sets of permutation $\beta_1, \beta_2, \beta_3$ (each of them has $k$ permutations). We can check by constructing direct product, but it is not efficient.
Suppose, $G^{P} =H$ where $P$ is an isomorphism. Let, $P$ is a direct product of permutations $\pi_1, \pi_2, \pi_3$ where $\pi_1$ permutes vertices of $G_1$, $\pi_2$ permutes vertices of $G_2$, $\pi_3$ permutes vertices of $G_3$. In other words, $\pi_i$ acts on $G_i$ such that $G$ transforms to graph $H$.
Now, assume there is an oracle that gives you a set of $n$ permutations for each $G_i$. Say, the set is $\beta_i$. In these $n$ permutations, one is $\pi_i$. So, you know , there is permutation that transform subgraph $G_i$ to $H_i$, but you don't know which one. If you just find all possible direct product, you will know, but that is exponential, thus inefficient.
A relevant question is asked here.
