The simultaneous conjugacy problem in the symmetric group

The transitive simultaneous conjugacy problem asks whether there exists a permutation $\tau \in S_n$ such that $b_j={\tau }^{-1}{a}_j\tau$ holds for all $j=1,2,\dots ,d$, where $a_1,a_2,\dots ,a_d$ and $b_1,b_2,\dots ,b_d$ are given sequences of $d$ permutations in $S_n$, each of which generates a transitive subgroup of $S_n$. As from mid 70’ it has been known that the problem can be solved in $O(d{n}^2)$ time. An algorithm with running time $O(dn \log(dn))$, proposed in late 80’, does not work correctly on all input data. In this paper we solve the transitive simultaneous conjugacy problem in $O(n^2 \log d / \log n + dn\log n)$timeand$O(n^{3/ 2} + dn)$ space. Experimental evaluation on random instances shows that the expected running time of our algorithm is considerably better, perhaps even nearly linear in $n$ at given $d$.