Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups

Abstract

In this paper, we investigate the complexity of computing minimal faithful permutation representations for groups without abelian normal subgroups (a.k.a. Fitting-free groups). When our groups are given as quotients of permutation groups, we exhibit a polynomial-time algorithm for constructing such representations. Furthermore, in the setting of permutation groups, we obtain an $\text{NC}$ procedure for computing the minimal faithful permutation degree, and a randomized $\text{NC}$ ($\text{RNC}$) algorithm for computing a minimal faithful permutation representation. This improves upon the work of Das and Thakkar (STOC 2024, SIAM J. Comput. 2026), who established a Las Vegas polynomial-time algorithm for computing the minimal faithful permutation degree for this class in the setting of permutation groups.

In [v3], we computed the minimal faithful permutation degree. For this new version [v4], we also compute a minimal faithful permutation representation. Version [v3] corresponds to our FCT 2025 paper