1
$\begingroup$

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$


STAB

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\}$

ISO

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

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

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.