A subquadratic algorithm for the simultaneous conjugacy problem

Abstract

The $d$-Simultaneous Conjugacy problem in the symmetric group $S_n$ 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 permutations in $S_n$. The time complexity of existing algorithms for solving the problem is $O(d{n}^2)$. We show that for a given positive integer $d$ the $d$-Simultaneous Conjugacy problem in $S_n$ can be solved in $o(n^2)$ time.