The Simultaneous Conjugacy Problem in the symmetric group $S_N$

I'll only consider the case of $S_N$ to start with.

Given $(g_1,\ldots,g_d)\in S_N^d$, define a directed graph $G$ on vertices $\lbrace 1,\ldots,N\rbrace$ whose edges are coloured with elements of $Z_2^d$. Edge $i{\to}j$ is coloured $(\epsilon_1,\ldots,\epsilon_d)$, where $\epsilon_t=1$ iff $g_t$ maps $i$ onto $j$. You can remove loops and edges of colour 0 if you like.

The isomorphism type of the graph $G$ exactly corresponds to the conjugacy class of $(g_1,\ldots,g_d)$, so you can use graph isomorphism software to find a canonical form together with the conjugacy that produces it. Generators for the centraliser too, if you want it.

This will be possible in practice for very large examples (say $dN$ up to several million), but whether it is competitive with other methods will depend on the size of your typical example. If $N$ is small it will take milliseconds. What typical values of $N$ and $d$ are you interested in?

Instead of $S_N$, any permutation group which is the full automorphism group of some graph (in its action on vertices) can be handled too, by adding that graph as an extra layer. More general permutation groups are harder.

ADDED: Going back to $S_N$, I'll give a polynomial time algorithm, confusingly using both group and graph terminology all mixed up. First, if $\langle g_1,\ldots,g_d \rangle$ is intransitive (the graph is disconnected), canonically label each component separately and list them in lexicographic order. So now assume connectivity.

For each vertex $v$, we can make a unique labelling $\ell(v)$ of the graph by starting at $v$ and scanning the graph in a deterministic way. There are many possibilities; I'll describe a version of breadth-first search. You have a queue (first-in, first-out store) $Q$, initially containing only $v$. Repeatedly do this: remove the vertex at the head of the queue, say $x$, then push into $Q$ (at the tail) those of $x^{g_1},\ldots,x^{g_d}$ (in that order) which have never previously been put into $Q$. Since the graph is strongly connected (being a union of directed cycles), every vertex is put into $Q$ eventually. Stop when that has happened and define $\ell(v)$ to be the order in which vertices were put into $Q$. Relabelling the vertices in the order they are listed in $\ell(v)$ to get a labelled graph $G(v)$. (This corresponds to $(g_1^\gamma,\ldots,g_d^\gamma)$ where $\gamma$ is the permutation mapping the old labels to the new labels.)

Now you have $G(v)$ for each $v$. Choose the lexicographically smallest and that is your canonical labelling of the graph. Each scan takes $O(Nd)$ time and there are $N$ scans, so the total time is $O(N^2d)$.

Several observations will speed it in practice. (1) You can restrict the starting points of scans to vertices minimising some combinatorial invariant (for example the list of cycle lengths of $g_1,\ldots,g_d$ that involve the vertex). This might greatly reduce the typical number of scans. (2) As all scans except the first are being made, compare the graphs as you go. It might allow some scans to stop early. (3) If $G(v)$ and $G(w)$ are identical (not just isomorphic) you have found an element of the centraliser. You can use such elements to avoid some scans by proving their starting vertices are equivalent to those you already used. (4) Even though I talked about the graph, I wouldn't actually construct it but would work directly with lists of permutations.

The graph is actually a deterministic finite automaton (at most one edge of each colour leaves each vertex). There could be faster isomorphism algorithms out there for DFAs, though I'm dubious that anything would work faster in practice than a well-tuned implementation of the method I described.

I used the same algorithm in several papers. I was unable to find older references, but given how simple the algorithm is, I'm sure they must exist.

arXiv:1604.08158 (section 4.3, implementation of UniqueRepresentative available at [1] in the references)

http://diginole.lib.fsu.edu/islandora/object/fsu%3A254453 (page 37)

arXiv:1305.7218 (section 4.3)

arXiv:1212.3803 (mentioned on page 12, implementation available at [23] in the references)