Two-closure of rank \(3\) groups in polynomial time (Q6170785)

Let \(G\) be a permutation group on a finite set \(\Omega\). The orbits of \(G\) on \(\Omega \times \Omega\) are called \(2\)-orbits. The set of \(2\)-orbits of \(G\) forms a coherent configuration. The number of \(2\)-orbits is called the rank of \(G\). The largest permutation group (acting on \(\Omega\)) having the same \(2\)-orbits as \(G\) is called the \(2\)-closure of \(G\) and is denoted by \(G^{(2)}\). Given generators of a rank \(3\) group \(G\), the paper under review provides a polynomial-time algorithm (in \(|\Omega|\)) to compute generators for \(G^{(2)}\). In many cases, not only \(G^{(2)}\) is constructed but the corresponding rank \(3\) graph is also recognized. The work is related to the graph isomorphism problem, in particular to the problem of computing generators of the full automorphism group of a given graph (see [\textit{R. Mathon}, Inf. Process. Lett. 8, 131--132 (1979; Zbl 0395.68057)]). In this context \(G^{(2)}\) was computed for \(G\) a group of odd order [\textit{S. Evdokimov} and \textit{I. Ponomarenko}, Discrete Math. 235, No. 1--3, 221--232 (2001; Zbl 0982.20005)], for a nilpotent group [\textit{I. N. Ponomarenko}, Appl. Algebra Eng. Commun. Comput. 5, No. 1, 9--22 (1994; Zbl 0803.20003)], for a \(3/2\)-transitive group [\textit{A. V. Vasil'ev} and \textit{D. V. Churikov}, Sib. Math. J. 60, No. 2, 279--290 (2019; Zbl 1512.20006); translation from Sib. Mat. Zh. 60, No. 2, 360--375 (2019)], and for a supersolvable group [\textit{I. Ponomarenko} and \textit{A. Vasil'ev}, Comput. Complexity 29, No. 1, Paper No. 5, 33 p. (2020; Zbl 1484.20002)].