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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you elaborate/clarify? I am having trouble understanding your question. $\endgroup$
    – verret
    Jun 5, 2016 at 4:48
  • $\begingroup$ @verret , I have added an example, please, have look. $\endgroup$
    – Michael
    Jun 5, 2016 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, 2016 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$
    – Michael
    Jun 5, 2016 at 10:51

0

Reset to default