There is an well known algorithm given by E.M Luks for bounded graph isomorphism. There are three important steps of the algorithm two of them are given below:

  1. If the group action on vertex set of input graph is transitive (single orbit) then solve the isomorphism problem in each coset:

$$ISO(G,X,Y) = ISO(K_i\sigma_1,X,Y) \cup ISO(K_i\sigma_2,X,Y)\cdots ISO(K_i\sigma_k,X,Y)$$

where $k$ is number of cosets. The $K_i$ is a kernel of group action $\pi : G \times B \mapsto B$.

  1. If the group action on vertex set of input graph is not transitive and let $B_1,B_2,\cdots B_l$ are the orbits (see group action $\pi$). Then we solve problem in each orbit : $$ISO_B(K_i\sigma_1,X,Y)=ISO_{B_{1}} (ISO_{B_{2}}\cdots ISO_{B_l}(K_i\sigma_1))$$

Questions :

  1. From step we will be getting the solutions , but how to patch these all solutions to get a solution to original problem.

  2. In step set $B = \{B_1,B_2, \cdots, B_l\}$ is a collection of orbits , If $B$ is a minimal system of imprimitivity then (step 2) still works or not.

  • $\begingroup$ Question 2 is very unclear. $B$ is a set of sets, how can it be a collection of partitions? Each $B_i$ is stabilized by $G$, hence $B$ is obviously $G$-invariant. Please clarify your question. Further, note that $G$ doesn't act on the set of vertices but on the collection of subsets of vertices (see the definition of $A$ in the original paper). $\endgroup$ Oct 20, 2017 at 17:04
  • $\begingroup$ @ Mikhail Tikhomirov I have edited the question $\endgroup$
    – fddwd
    Oct 20, 2017 at 17:42

1 Answer 1

  1. We know that each $ISO$ is either a coset or an empty set. Suppose that non-empty answers to children $ISO$'s are cosets $g_i H_i$. Take $g_1$ as a representative for the resulting coset, then the subgroup $H$ corresponding to the resulting coset is induced by $g_1^{-1}g_i h_i$, where $h_i$ ranges over generators of $H_i$.

  2. No, why would it work? The transitive case is treated with enumerating elements of the primitive action on the minimal system of imprimitivity (and corresponding cosets of the action kernel) rather than with direct restriction to the blocks, so the question seems totally irrelevant to the understanding of the algorithm.

  • $\begingroup$ TikhomirovAbout your second answer. My second is motivated from the thesis of Paulo codenotti , see page no - 48, section -3.4.2, first paragraph, last line. I may have misunderstood this thing. $\endgroup$
    – fddwd
    Oct 21, 2017 at 4:30
  • $\begingroup$ people.cs.uchicago.edu/~laci/students/codenotti.pdf $\endgroup$
    – fddwd
    Oct 21, 2017 at 5:37
  • $\begingroup$ This note refers to the fact that $K_i$ stabilizes each block, hence the next step after splitting $G$ into cosets will always be the intransitive step. $\endgroup$ Oct 21, 2017 at 7:47
  • $\begingroup$ @ Mikhail Tikhomirov I have edited the second case. $\endgroup$
    – fddwd
    Oct 21, 2017 at 8:16
  • $\begingroup$ I fail to see the point of this edit, just as well as the point of the question. Step 2 has nothing to do with systems of primitivity. $\endgroup$ Oct 21, 2017 at 8:22

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.