Graph isomorphisms in quasi-polynomial time

Authors Harald A. Helfgott, Jitendra Bajpai, Daniele Dona

Publication date 12 October 2017

Group actions on combinatorial structures (05E18) Primitive groups (20B15) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Let us be given two graphs

G a m m a_{1}

,

G a m m a_{2}

of

n

vertices. Are they isomorphic? If they are, the set of isomorphisms from

G a m m a_{1}

to

G a m m a_{2}

can be identified with a coset

H c d o t p i

inside the symmetric group on

n

elements. How do we find

p i

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

e x p l e f t (O (l o g n)^{O (1)} i g h t)

. His strategy is based in part on the algorithm by Luks (1980/82), who solved the case of graphs of bounded degree.

This page was built for publication: Graph isomorphisms in quasi-polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6292482)