Finding a cycle base of a permutation group in polynomial time (Q724293)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding a cycle base of a permutation group in polynomial time |
scientific article |
Statements
Finding a cycle base of a permutation group in polynomial time (English)
0 references
25 July 2018
0 references
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.
0 references
Cayley graph
0 references
cycle base
0 references
automorphism group
0 references
canonical labeling
0 references
polynomial-time algorithm
0 references
0 references