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:
- 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$.
- 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 :
From step we will be getting the solutions , but how to patch these all solutions to get a solution to original problem.
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.