# Hypergraph Isomorphism for Groups with Restricted Composition Factors

arXiv: https://arxiv.org/abs/2002.06997 · HTML: https://mlsanity.com/paper/2002.06997/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 1 of 1)

- [Instruction Set and Language for Hypergraphs](https://mlsanity.com/paper/2607.10194/) (2026)

## Abstract (arXiv)

We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices V and a permutation group Gamma over domain V, and asking whether there is a permutation γ ∈ Gamma that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on d points, this problem can be solved in time (n+m)^O((log d)c) for some absolute constant c where n denotes the number of vertices and m the number of hyperedges. In particular, this gives the currently fastest isomorphism test for hypergraphs in general. The previous best algorithm for this problem due to Schweitzer and Wiebking (STOC 2019) runs in time nO(d)mO(1). As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding K3,h (h ≥ 3) as a minor in time n^O((log h)c). In particular, this gives an isomorphism test for graphs of Euler genus at most g running in time n^O((log g)c).