pith. sign in

arxiv: 1710.04574 · v1 · pith:IT5HY6FGnew · submitted 2017-10-12 · 🧮 math.GR

Graph isomorphisms in quasi-polynomial time

classification 🧮 math.GR
keywords gammatimealgorithmgraphsisomorphismsquasi-polynomialtheyalways
0
0 comments X
read the original abstract

Let us be given two graphs $\Gamma_1$, $\Gamma_2$ of $n$ vertices. Are they isomorphic? If they are, the set of isomorphisms from $\Gamma_1$ to $\Gamma_2$ can be identified with a coset $H\cdot\pi$ inside the symmetric group on $n$ elements. How do we find $\pi$ and a set of generators of $H$? The challenge of giving an always efficient algorithm answering these questions remained open for a long time. Babai has recently shown how to solve these problems -- and others linked to them -- in quasi-polynomial time, i.e. in time $\exp\left(O(\log n)^{O(1)}\right)$. His strategy is based in part on the algorithm by Luks (1980/82), who solved the case of graphs of bounded degree.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A Hierarchy of Tinhofer Graphs: Separations and Membership Testing

    cs.CC 2026-05 unverdicted novelty 7.0

    Introduces the k-Tinhofer hierarchy between general graphs and Tinhofer graphs, gives algebraic and combinatorial characterizations, proves strict separations for each k, shows P-hardness of deciding membership in the...

  2. On circulant ternary coherent configurations of prime degree

    math.CO 2026-04 unverdicted novelty 6.0

    Any circulant ternary coherent configuration of prime degree p is schurian, except possibly when it is an association scheme on triples with Aut(X) equal to AGL1(p) for p ≡ ±1 mod 8 or a proper subgroup thereof.