Abstract. The minimal faithful permutation degree [Formula: see text] of a finite group [Formula: see text] is the smallest integer [Formula: see text] for which there is an injective homomorphism [Formula: see text] from [Formula: see text] to [Formula: see text]. The main result of this paper is a randomized polynomial-time algorithm for computing the minimal faithful permutation degree groups without abelian normal subgroups. Additionally, we show that: 1. For any primitive permutation group [Formula: see text], [Formula: see text] can be computed in quasi-polynomial time. 2. For a group [Formula: see text] given by its Cayley table, [Formula: see text] can be computed in [Formula: see text].

The isomorphism problem for graphs (GI) and the isomorphism problem for groups (GrISO) have been studied extensively by researchers. The current best algorithms for both these problems run in quasipolynomial time. In this paper, we study the isomorphism problem of graphs that are defined in terms of groups, namely power graphs, directed power graphs, and enhanced power graphs. It is not enough to check the isomorphism of the underlying groups to solve the isomorphism problem of such graphs as the power graphs (or the directed power graphs or the enhanced power graphs) of two nonisomorphic groups can be isomorphic. Nevertheless, it is interesting to ask if the underlying group structure can be exploited to design better isomorphism algorithms for these graphs. We design polynomial time algorithms for the isomorphism problems for the power graphs, the directed power graphs and the enhanced power graphs arising from finite nilpotent groups. In contrast, no polynomial time algorithm is known for the group isomorphism problem, even for nilpotent groups of class 2. We note that our algorithm does not require the underlying groups of the input graphs to be given. The isomorphism problems of power graphs and enhanced power graphs are solved by first computing the directed power graphs from the input graphs. The problem of efficiently computing the directed power graph from the power graph or the enhanced power graph is due to Cameron [IJGT'22]. Therefore, we give a solution to Cameron's question.

Cayley’s theorem says that every finite group G can be viewed as a subgroup of a symmetric group Sm for some integer m. The minimal faithful permutation degree µ(G) of a finite group G is the smallest integer m such that there is an injective homomorphism φ from G to Sm. The main result of this paper is a randomized polynomial time algorithm for computing the minimal faithful permutation degree of semisimple permutation groups. Semisimple groups are groups without any abelian normal subgroups. Apart from this, we show that: 1. For any primitive permutation group G, µ(G) can be computed in quasi-polynomial time. 2. Given a permutation group G and an integer k, the problem of deciding if µ(G) ≤ k is in NP. 3. For a group G given by its Cayley table, µ(G) can be computed in DSPACE(log3 |G|).

A finite group of order n can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order n can be stored using O(n²) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order n that uses o(n²) space but can still answer a multiplication query in constant time. We design a constant query-time data structure that can store any finite group using O(n) words where n is the order of the group. Farzan and Munro (ISSAC 2006) gave an information theoretic lower bound of Ω(n) on the number of words to store a group of order n. Since our data structure achieves this lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonableian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups (CFSG).

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism, denoted CHI, which has running time (2 b N) O(1), where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe an fpt algorithm for a parameterized coset intersection problem that is used as a subroutine in our algorithm for CHI.

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results: • Isomorphism for bounded tree distance width graphs is in L and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace. • For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e. when only isomorphisms are considered, mapping bags in one decomposition blockwise onto bags in the other decomposition) is in L. • For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in LogCFL. • As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the known TC 1 upper bound for the problem given by Grohe and Verbitsky.

Reachability and shortest path problems are \NLC\ for general graphs. They are known to be in \Log\ for graphs of tree-width $2$ \cite{JT07}. However, for graphs of tree-width larger than $2$, no bound better than \NL\ is known. In this paper, we improve these bounds for $k$-trees, where $k$ is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed $k$-trees, and for computation of shortest and longest paths in directed acyclic $k$-trees. Besides the path problems mentioned above, we consider the problem of deciding whether a $k$-tree has a perfect macthing (decision version), and if so, finding a perfect matching (search version), and prove that these problems are \Log-complete. These problems are known to be in \Ptime\ and in \RNC\ for general graphs, and in \SPL\ for planar bipartite graphs \cite{DKR08}. Our results settle the complexity of these problems for the class of $k$-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from \cite{JT07} and \cite{LMR07}.