1
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by user1688, Jan-Christoph Schlage-Puchta, Stefan Kohl, Neil Strickland, Alex Degtyarev Jun 9 '16 at 20:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Could you elaborate/clarify? I am having trouble understanding your question. $\endgroup$ – verret Jun 5 '16 at 4:48
  • $\begingroup$ @verret , I have added an example, please, have look. $\endgroup$ – Jim Jun 5 '16 at 6:02
  • $\begingroup$ If there are $n$ permutations for each of three subgraphs, then checking all possibilities is $O(n^3)$, not exponential. Or are you interested in this question for arbitrarily large values of $3$? $\endgroup$ – Adam P. Goucher Jun 5 '16 at 10:49
  • $\begingroup$ @AdamP.Goucher, $3$ is for an illustration, graph has $x=n/c$ subgraphs, in general, where $n$ is the number of vertices of $graph$ and $c$ is a constant. $\endgroup$ – Jim Jun 5 '16 at 10:51