Notations :

AUT$(X)$ (where $X$ is a graph) is the group of automorphisms of the graph $X$

$G=\langle A \rangle $ means group $G$ is generated by set $A$.

$G_{\{\Delta\}}$ is the set-wise stabiliser of $\Delta$


Input : $A \subseteq \text{Sym}(\Omega)$ and $\Delta \subseteq \Omega$

Find : Generator of $\langle A \rangle_{\{\Delta\}} = \{g \in \langle A \rangle \mid \Delta ^ g = \Delta\}$


Given : $X_1 = (V,E_1)$ and $X_2 = (V,E_2)$

Find : Is $X_1$ isomorphic to $X_2$?

Claim : ISO $\le_{P}$ STAB ( polynomial time reduction )

  1. Proof : Take disjoint union $X=X_1 \cup X_2$ and note that AUT$(X) \le \text{Sym}(V) =G$

  2. $G$ acts on the set $V \choose 2$ i.e. set of all unordered pair of vertices. Clearly $E \le$ $V \choose 2$ and AUT$(X) = G_{\{E\}}$ under the above group action.

Question : Is this a polynomial time reduction from decision problem to non-decision problem? Please note that It is possible that I may have misunderstood the reduction

Reference : Poly time computation in groups by E.M Luks See Page no 3


1 Answer 1


It seems that the author uses the notation $A\le_p B$, where $A,B$ can be either function or decision problems, for saying that given an oracle for $B$, one can solve $A$ in polynomial time.

It is then shown that the isomorphism problem is reducible to finding the generators of a setwise stabilizer group (STAB) by showing that it is reducible to finding the generators of the automorphism group (AUT), and that $AUT\le_p STAB$. The latter is shown by viewing vertex permutations as an operation over vertex pairs, and seeking the generators of the corresponding stabilizing group relative to $E$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.