Finding a cycle base of a permutation group in polynomial time (Q724293)

A cycle base \(B\) of a permutation group \(K\leq\mathrm{Sym}(n)\) is a set of representatives of the conjugacy classes of regular cyclic subgroups \(G\) of \(K\). In earlier papers the authors have described efficient algorithms in recognition and isomorphism testing of circulant graphs under the hypothesis that cycle bases are given (see [\textit{S. A. Evdokimov} and the second author, St. Petersbg. Math. J. 15, No. 6, 813--835 (2004; Zbl 1061.05045); translation from Algebra Anal. 15, No. 6, 1--34 (2003)] and [the first author, Proc. Lond. Math. Soc. (3) 88, No. 1, 1--41 (2004; Zbl 1045.05052)]). In the present paper, they show that there exists a \(\mathrm{poly}(n)\) algorithm to construct a cycle base for a subgroup of \(\mathrm{Sym}(n)\) defined by a generating set whose size is polynomial in \(n\). The major step to prove this result depends on showing that there exists a \(\mathrm{poly}(n)\) algorithm to construct a solvable subgroup \(K_{0}\leq K\) such that every regular cyclic subgroup of \(K\) is \(K\)-conjugate to a subgroup of \(K_{0}\). In particular, it follows that, given a combinatorial object \(X\) on \(n\) points and its automorphism group \(\mathrm{Aut}(X)\), it is possible to decide whether \(X\) is a circulant object in time \(\mathrm{poly}(n)\); if so, a complete system of pairwise nonequivalent circulant representations of \(X\) can be constructed.