Graph Isomorphism in Quasipolynomial Time

László Babai

Source-linked AI summary

Graph Isomorphism in Quasipolynomial Time

László Babai

arXiv:1512.03547v2Dec 11, 2015cs.DScs.CCmath.COmath.GR

TL;DR

The paper addresses whether GI, SI, and CI can be solved more efficiently than their previous subexponential bounds. It extends Luks’s framework with local certificates and canonical partitioning, obtaining quasipolynomial-time algorithms and identifying Johnson graphs as the only obstructions to effective partitioning in the stated sense.

Problem
GI, SI, and CI previously had bounds of roughly exp(Õ(√n)), motivating improved algorithms and structural handling of Luks’s barrier groups.
Method
The algorithm combines Luks’s framework with local certificates, group-theoretic divide-and-conquer, and combinatorial canonical partitioning.
Results
String Isomorphism, Graph Isomorphism, and Coset Intersection can be solved in quasipolynomial time.
Takeaways & Limitations
Johnson graphs are the only obstructions to effective canonical partitioning in the paper’s stated sense.
Takeaways & Limitations
The stated analysis depends on CFSG through Cameron’s classification and Schreier’s Hypothesis, although Cameron’s result can be dispensed with using combinatorial partitioning.

Abstract

from arXiv · show

We show that the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (under group action) (SI) and Coset Intersection (CI) can be solved in quasipolynomial ($\exp((\log n)^{O(1)})$) time. The best previous bound for GI was $\exp(O(\sqrt{n\log n}))$, where $n$ is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, $\exp(\tilde{O}(\sqrt{n}))$, where $n$ is the size of the permutation domain (Babai, 1983). The algorithm builds on Luks's SI framework and attacks the barrier configurations for Luks's algorithm by group theoretic "local certificates" and combinatorial canonical partitioning techniques. We show that in a well-defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. Luks's barrier situation is characterized by a homomorphism φ that maps a given permutation group $G$ onto $S_k$ or $A_k$, the symmetric or alternating group of degree $k$, where $k$ is not too small. We say that an element $x$ in the permutation domain on which $G$ acts is affected by φ if the φ-image of the stabilizer of $x$ does not contain $A_k$. The affected/unaffected dichotomy underlies the core "local certificates" routine and is the central divide-and-conquer tool of the algorithm.

1 Introduction

The paper gives quasipolynomial algorithms for String Isomorphism, Graph Isomorphism, and Coset Intersection by extending Luks’s framework with local certificates, divide-and-conquer, and canonical partitioning. Its central structural insight is that affected orbits enable group-theoretic reduction, while Johnson graphs characterize the main obstruction to effective partitioning.

Results: Quasipolynomial algorithms solve String Isomorphism, Graph Isomorphism, and Coset Intersection.The String Isomorphism result is polynomial in string length and quasipolynomial in the largest orbit length; vertex-colored GI is quasipolynomial in the largest color multiplicity.
Local to global: Local certificates alternate between detecting local symmetry and deriving global automorphisms or local obstructions to symmetry.The method uses lower and upper approximations of the automorphism group, with combinatorial partitioning tightening the upper bound.
Approach: The approach builds on Luks’s framework with a group-theoretic result, a divide-and-conquer algorithm, and two combinatorial partitioning algorithms.Local certificates implement the central group-theoretic and combinatorial ideas.
Group-theoretic divide-and-conquer: Affected orbits force the kernel of a giant representation to be nontransitive, with every kernel orbit having length at most |∆|/k.This structural result supplies the principal divide-and-conquer mechanism.
Combinatorial partitioning: Johnson graphs are the only stated obstructions to effective partitioning: either partitioning succeeds or a canonically embedded Johnson graph covers at least 0.9n vertices.The partitioning theorem instead provides a coloring with small classes, a large class with a nontrivial equipartition, or a large class containing a Johnson graph.
Combinatorial partitioning: The partitioning procedure finds a suitable structure at quasipolynomial multiplicative cost, and its analysis is almost entirely combinatorial with modest elementary group theory.The existence of the structure can also be deduced from CFSG, while the algorithm can dispense with Cameron’s result.

2 Preliminaries

This section establishes notation for finite permutation groups, their actions, stabilizers, orbits, invariant partitions, and induced representations. It also introduces relational structures and coherent-configuration tools used in the paper’s graph-isomorphism analysis.

Permutation groups: Permutation groups act on domains through homomorphisms into symmetric groups, with the image describing the induced action and giant actions containing an alternating group.The domain size is the representation degree; the group’s order is distinct from this degree.
Permutation groups: Stabilizers fix points, orbits collect their images, and invariant sets and partitions are unions of orbits or blocks permuted by the group.Blocks of imprimitivity and systems of imprimitivity organize transitive group actions into coarser structures.
Permutation groups: Primitive groups have no nontrivial blocks of imprimitivity, while doubly transitive groups act transitively on ordered pairs of distinct points.Johnson groups provide an important family of primitive groups in the paper’s setting.
Relational structures: Relational structures consist of a vertex set together with relations, and their induced substructures, skeletons, isomorphisms, and automorphism groups support graph-like representations.A k-ary relation is a subset of the k-fold Cartesian power of the vertex set.
Configurations and partitioning: UPCCs are obstacles to natural combinatorial partitioning, while the paper’s technical contribution is to overcome this obstacle.The paper also records structural properties of constituent digraphs, including equipartition by connected components and equal neighborhood sizes across corresponding components.
Johnson structures: For t ≥2 and m ≥2t + 1, the automorphism group of the Johnson graph J(m,t) is the induced symmetric-group action on t-sets.This identifies the symmetry group underlying the Johnson structures that recur in the paper.

3 Algorithmic setup

This section reviews Luks’s String Isomorphism framework, including window isomorphism, shift alignment, and recursive reductions through invariant partitions. It then identifies large primitive groups as barriers and reduces those barriers to Johnson groups, supporting a quasipolynomial recurrence.

String Isomorphism framework: String Isomorphism computes the set of permutations in a specified group or coset that map one string to another.The computation and decision versions are polynomial-time equivalent under Cook reductions.
Window reductions: Window-isomorphism restricts attention to a G-invariant subset while retaining the permutations’ action on the remainder.The framework assumes an invariant window and uses shift alignment when the ambient group is replaced by a coset or subgroup.
Window reductions: Strong Luks reduction processes invariant blocks sequentially, reducing one instance to m kernel-group instances at polynomial cost per instance.The reduction first uses the kernel of the induced action on blocks, then applies the chain rule to each block.
Johnson-group barrier: Large primitive permutation groups without well-behaved small-index subgroups are the main barrier to efficient Luks reductions.Cameron’s classification identifies the relevant large primitive groups, which can be reduced to Johnson groups.
Johnson-group barrier: A primitive group of order at least 2^(1+log2 n) has a normal subgroup of index at most n whose induced action is a Johnson group, found in polynomial time.The associated Johnson parameter satisfies k ≥ log2 n.
Cost estimate: The algorithm’s ProcessJohnsonAction routine handles the reduced Johnson-group case, while the resulting recurrence resolves to T(x) = q(x)O(log x).The stated recurrence yields the desired quasipolynomial bound.

4 Functors, canonical constructions

This section formalizes canonical constructions using concrete categories and functors. It also defines reductions with multiplicative cost and explains how constructions can remain canonical relative to an arbitrary individualization choice.

Categories and functors: The paper models relational structures and their isomorphisms as concrete, faithful Brandt groupoids, with objects sharing underlying sets and morphisms represented by bijections.The framework covers graphs, hypergraphs, partitions, colored structures, and UPCCs.
Canonical constructions: A canonical assignment is the object mapping induced by a functor, so isomorphisms are transported consistently between constructed objects.Canonical embeddings additionally restrict each morphism to the embedded underlying subset.
Canonical constructions: A category of tuples collects a canonical set of individually noncanonical choices while preserving compatibility under isomorphisms.Its morphisms are unions of the isomorphisms between compatible choices, and the resulting structure is again a category.
Reductions: A reduction at multiplicative cost s maps each object to a tuple of s target objects, allowing an isomorphism problem to be solved through those instances.Efficient forward and inverse computation makes the total work essentially the cost of solving s target instances.
Relative canonicity: Individualization illustrates canonicity relative to a choice: after selecting t ordered vertices, a structure can be canonically embedded relative to that choice, with cost at most n^t.The same idea applies to vertices of canonically constructed auxiliary objects.

5 Breaking symmetry: colored partitions

This section develops canonical colored partitions as a symmetry-breaking tool. It refines partitions into equipartitions and studies induced colorings of tuple sets to obtain controlled reductions in class sizes.

Colored partitions: A colored partition assigns colors and within-color blocks, with admissibility requiring blocks of size at least 2 in nontrivial color classes.A colored equipartition additionally gives equal block sizes within each color class.
Colored partitions: Canonical colored partitions are functorial assignments preserved by isomorphisms, and they can be canonically refined to colored equipartitions without changing blocks.Block sizes are encoded into element colors during refinement.
Progress measure: An α-partition either keeps every color class at size at most αn or nontrivially partitions the unique dominant class larger than n/2.Finding canonical 4/5-partitions is identified as a key progress indicator.
Tuple colorings: A coloring of Γ induces a canonical coloring of its t-tuples in which every resulting color class is at most (2/3)|Φ|, except possibly one class.The bound is established inductively over the color classes of Γ.
Tuple colorings: Any α-coloring of Γ induces a max(2/3, α)-coloring of the corresponding tuple set for α < 1 and t ≥ 2.This combines the tuple-coloring bounds with the original maximum color-class size.
Progress measure: The resulting inequalities are repeatedly used to certify progress whenever the algorithm finds a canonical coloring of its auxiliary set Γ.The analysis derives these inequalities from the two-color case and induction.

6 Breaking symmetry: the Design Lemma

The Design Lemma reduces high-arity relational structures to useful canonical partitions or embedded UPCCs after individualizing few vertices. Its proof exploits coherent configurations, block-design arguments, and threshold monotonicity.

Design Lemma: The reduction first seeks a small canonical partition and otherwise restricts a large color class to a binary 2-skeleton, where it either splits or produces a UPCC.This is the paper’s first combinatorial symmetry-breaking tool for reducing k-ary structures to binary ones.
Design Lemma: The Design Lemma finds, in time nO(k), at most k − 1 vertices whose individualization yields either a canonical colored α-partition or a canonical embedded uniprimitive coherent configuration.The input has relative strong symmetry defect at least 1 − α, with 1/2 ≤ α < 1.
Thresholds: The Design Lemma is monotone in its threshold: proving it for α implies it for every α′ with 1 > α′ ≥ α ≥ 1/2.A returned α-partition remains an α′-partition, while an intermediate-sized embedded set yields an α′-coloring.
Proof strategy: If a primitive restricted configuration remains a clique configuration, individualizing vertices eventually exposes distinctions because no transposition inside the large class is an automorphism.Coherence detects whether a transposition belongs to Aut(X), while the symmetry-defect assumption rules out all such transpositions.
Proof strategy: In one case, the induced hypergraph is a regular block design, and Fisher’s inequality contradicts the sizes of its blocks and vertices.The contradiction uses |B| < (1 − α)n < n/2 and |C \ Q| > αn > n/2.
Local guides: The local-guide result transforms local asymmetry into canonical structures whose strong symmetry defect is at least n − k + 1.It either refutes isomorphism or produces canonical k-ary structures on the original underlying sets.

7 Split-or-Johnson

The section develops a Split-or-Johnson framework: canonical partitioning succeeds at quasipolynomial cost unless a large canonically embedded Johnson scheme remains. Johnson schemes are the formal obstruction because constant-factor canonical partitions can require exponential multiplicative cost.

Main dichotomy: The Split-or-Johnson algorithm returns either a canonical colored 3/4-partition or a canonically embedded Johnson scheme covering at least 3/4 of the vertices.This establishes Johnson schemes as the only obstruction to the desired partitioning outcome in the stated sense.
Johnson barriers: Johnson schemes are barriers to canonical α-partitions, requiring multiplicative cost at least (t/ε)^(εm/t) for J(m,t).For fixed t, obtaining a constant-factor reduction therefore has exponential cost in m.
Recursive framework: The combinatorial results are proved recursively through mutual reductions among UPCCs, colored bipartite graphs, relational structures, and colored partitions.The framework combines the Design Lemma with Theorem 7.3.1 as the overall partitioning tool.
Main dichotomy: Theorem 7.3.1 applies the dichotomy to UPCCs, while Theorem 7.3.2 applies it to colored bipartite graphs under size and symmetry-defect assumptions.Both outputs are obtained at quasipolynomial multiplicative cost and preserve the relevant large subset.
Main dichotomy: The Extended Design Lemma extends the result to k-ary relational structures, producing a canonical partition or a large embedded Johnson scheme at cost q(n)n^O(k).The Johnson scheme occupies a subset W with |W| ≥ αn.

7.4 Minor subroutines

The minor subroutines reduce UPCC and bipartite instances to canonical partitions or smaller structured instances. They use individualization, refinement, twin classes, and reductions between coherent configurations and colored bipartite graphs.

UPCC-to-bipartite: UPCC-to-bipartite either achieves a canonical partition or constructs a large canonically embedded semiregular bipartite graph for the bipartite theorem.The constructed first part has size at least βn, and solutions transfer back to the UPCC.
UPCC-to-bipartite: Individualizing a vertex partitions a UPCC into canonical relation-neighborhood subsets; if every subset is small, the desired partition is obtained.If some relation neighborhood exceeds βn, the procedure instead forms a semiregular bipartite graph.
Color and twin routines: For a bipartite graph without twins in V1, splitting V2 into two color-unions guarantees that one induced subgraph has symmetry defect at least 1−α.The guarantee follows because large symmetrical subsets in both induced graphs would create twins in the original graph.
Color and twin routines: Twins are same-part, same-color vertices with identical neighborhoods, and their equivalence classes directly yield canonical partitions when sufficiently large.In bipartite graphs, weak and strong twins coincide, so the distinction is unnecessary.
Bipartite routine: The Bipartite Split-or-Johnson procedure handles small instances by individualization or refinement, then recursively analyzes homogeneous, imprimitive, clique, and UPCC cases.Its input assumes |V2| < α|V1| and symmetry defect on V1 at least 1−α.

7.6 Measures of progress

The algorithm measures progress by shrinking an auxiliary side while preserving symmetry defect, using partitions, block reductions, and Johnson detection. In the block-design case, it either halves the auxiliary domain or terminates with a large Johnson scheme.

Progress measures: Major progress occurs when the auxiliary size n2 decreases, or when its configuration advances from clique to UPCC or from UPCC to Johnson scheme without growing.Throughout the procedure, n1 does not increase.
Imprimitive case: In the imprimitive case, selecting a component or contracting all components reduces n2 by at least half while retaining symmetry defect at least 1/2.The resulting contracted graph is semiregular, nonempty, and noncomplete, so Proposition 7.2.6 applies.
Imprimitive case: If all relevant neighborhood degrees are at most n1/2, individualizing a vertex yields a canonical colored 1/2-partition of V1.Otherwise, the algorithm focuses on a large-degree color and its induced component graphs.
Block design case: For a complete neighborhood hypergraph, the vertices form a canonically embedded Johnson scheme labeled by d1-subsets of V2, terminating the main algorithm.This is the Johnson outcome of the block-design analysis.
Block design case: When the hypergraph has large symmetry defect and bounded degree, the Design Lemma returns either a 3/4-partition or a UPCC on at least 3/4 of V2.The latter is a significant reduction because subsequent processing uses a smaller structured instance.

7.9 UPCC

In the UPCC case, the algorithm applies the UPCC-to-bipartite reduction to obtain either a canonical partition and domain reduction or a smaller structured instance. A Johnson outcome is handled by reducing the complementary or selected part and recursing.

UPCC reduction: Applying UPCC-to-bipartite with α=2/3 yields either a canonical colored 2/3-partition of V2 or a canonically embedded nontrivial semiregular bipartite graph.The reduction is used when X2 is uniprimitive but not known to be Johnson.
UPCC reduction: A returned canonical colored 2/3-partition is processed by Reduce-Part2-by-Color to reduce V2 to one color class.The reduction is treated as significant progress.
UPCC reduction: The semiregular bipartite outcome has a first part of size at least 2/3 of V2 and a second part of size at most |V2|/3.This produces a significantly smaller instance while preserving the relevant structure.
Johnson outcome: If the procedure returns a Johnson scheme on at least 2/3 of V2, the algorithm either recurses on the complement or enters the explicit Johnson-scheme subcase.Selecting the complement reduces n2 by a factor of 3.

7.10 Local to global symmetry

The local-to-global symmetry lemma shows that uniformly high symmetry in all sufficiently small induced subhypergraphs forces the entire uniform hypergraph to retain that symmetry bound.

Exchange/augment: An exchange/augment lemma extends a highly symmetric set A by one element from B when |A| > (t + 1)|B| and each deletion of an element of A can be repaired from B.The conclusion is that some v ∈ B makes S(A ∪ {v}) a subgroup of Aut(H).
Exchange/augment: The exchange proof uses the pigeon-hole principle to find u ∈ B associated with at least t + 2 elements of A, then verifies the transposition swapping x and u preserves every edge.A suitable y can be chosen outside the tested edge and x.
Local to global symmetry: Every induced subhypergraph on ℓ vertices having symmetry defect at most s implies the full t-uniform hypergraph has defect at most s.Here ℓ = max{t+3, (t+2)(t+3)s}.
Inductive proof: The proof inducts from subsets of size ℓ to larger subsets by preserving condition (C_k), which bounds each induced subhypergraph’s symmetry defect.The induction proceeds for k = ℓ, ℓ+1, ..., m.
Inductive proof: Applying the exchange argument to a minimal exceptional subset B proves |B| ≤ s and completes the inductive step.The contradiction comes from enlarging the complement of B while preserving its full symmetric action.

7.11 Bipartite graph with Johnson scheme on small part

This section develops recursive canonical partitioning for bipartite graphs whose smaller side is a Johnson scheme, using colorings, equipartitions, relational designs, and UPCC decompositions to obtain significant reductions.

Setup: The algorithm seeks a canonical colored α-partition of V1 while treating each neighborhood as a t-uniform hypergraph on Γ.It first colors vertices by neighborhood size and recursively restricts to the largest color class when necessary.
Case 1: A canonical coloring of Γ is found: Small Γ can be fully individualized, which distinguishes every vertex of V2 and then every twin-free vertex of V1.This is used when m ≤ 2ℓ.
Cases 1–2: A canonical coloring or equipartition of Γ induces partitions of V2 by intersection profiles, with nontrivial blocks handled by the imprimitive-case procedure.The construction uses ordered or unordered partitions of t across the color classes or blocks of Γ.
Case 2: A canonical equipartition of Γ is found: Good partitions reduce Γ to a part of size at most 3m/4, while the remaining Johnson case recursively reduces the underlying domain or returns a smaller V2.The Johnson reduction is significant when the selected Γ-part is sufficiently smaller than Γ.
Cases 3–4: A canonical ℓ-ary relation with strong symmetry defect triggers the Design Lemma, which either yields a colored partition or a large UPCC for further recursive splitting.The UPCC case uses the Split-or-Johnson machinery with parameter β = 3/4.
Case 5: Johnson scheme: In the final Johnson configuration, Weisfeiler–Leman canonically produces a 1/6-partition of V2 from the coloring of overlapping neighborhood hypergraphs.The partition separates configurations with disjoint edges from the remainder and equipartitions the former by their unions.

8 Alternating quotients of a permutation group

The section analyzes large alternating quotients of permutation groups and derives structural consequences for affected points, stabilizers, and canonical systems of imprimitivity.

Motivation: Luks’s barrier arises from large primitive groups lacking well-behaved small-index subgroups, with Johnson groups identified as the relevant obstruction.The paper’s contribution is to break this symmetry using group-theoretic structure.
Affected and unaffected points: For a giant representation, a point is affected when its stabilizer’s image does not contain A(Γ), and unaffected points retain a full alternating or symmetric image under their collective pointwise stabilizer.This Unaffected Stabilizer Theorem supplies the basis for LocalCertificates.
Primitive groups: When k > max{8, 2 + log2 n}, a primitive group surjecting onto A_k must be isomorphic to A_k.Thus the alternating quotient is not merely a quotient in the primitive case.
Tightness: The threshold k > 2 + log2 n is tight: affine examples at equality show that the conclusions can fail infinitely often.In even characteristic, A_k acts on a quotient of a zero-weight subspace with k = 2 + log2 n.
Affected and unaffected points: An affected orbit has kernel orbits of length at most |∆|/k, giving a concrete reduction in the action of the quotient kernel.This is the Affected Orbit Lemma for k ≥ 5.
Main structure theorem: For sufficiently large alternating quotients, the group’s action decomposes into canonical standard blocks labeled by subsets of [k], with Johnson-group action on those blocks.The Main Structure Theorem also characterizes affected points through the size of their associated subset T(x).
Main structure theorem: The standard blocks can be found in polynomial time, and the quotient action is either a Johnson group when t∆ ≥ 1 or trivial when t∆ = 0.This provides an explicit computational form of the structural decomposition.

9 Verification of top action

The verification procedures test whether a string automorphism or isomorphism projects onto a giant action and, when it does, recover the isomorphism through recursive smaller String Isomorphism instances.

Top-action verification: The top-action procedure recognizes whether a giant representation remains giant on Aut_G(x) and can recover Iso_G(x,y).It uses O(m) recursive calls on windows of size at most n/m.
Lifting: Lifting reduces questions about a homomorphism image to String Isomorphism instances for the kernel, using coset generators and constructive membership operations.The framework permits polynomial-time manipulation of generated subcosets.
Top-action verification: When the projected isomorphism set is a giant coset, the procedure decides isomorphism and finds Iso_G(x,y); if it is not giant, non-isomorphism follows.The latter implication uses the coset structure Iso_G(x,y) = Aut_G(x)σ when an isomorphism exists.
Top-action verification: The alternating-image case uses three kernel-isomorphism instances, while the symmetric-image case first applies weak Luks reduction through the alternating preimage.The resulting recursion uses windows of size n/k for m ≤ k ≤ n.
Canonical color classes: A canonical coloring with a giant restriction on a color class larger than half of Γ enables recovery through at most 6k recursive instances.The remaining color classes are then processed by the Chain Rule.
Canonical color classes: The procedure’s recurrence can be generously bounded by 6T(2n/3), reflecting the reduced size of remaining color classes.The 2n/3 bound comes from the cited lemma on the remaining classes.

10 The method of local certificates

The local-certificates method grows a window of affected domain elements and uses it to produce verifiable certificates of fullness or non-fullness. These certificates support canonical partitioning and recursive reductions to smaller String Isomorphism instances.

The core algorithm processes an imprimitive group using a group-theoretic divide-and-conquer method.
For test sets with max{8, 2 + log2 n} < k ≤ m/10, local certificates require at most k!n2 smaller String Isomorphism calls and k! poly(n) additional computation.The smaller instances have domains of size at most n/k.
For a giant representation, the algorithm tracks affected elements, whose stabilizer image fails to contain the alternating group.Affected elements form invariant orbits, and all elements in an affected orbit share the property.
The algorithm grows a window by adding elements affected by the current stabilizer, then recomputes the subgroup preserving the string on that window.The window starts empty; the subgroup decreases as more of the input is incorporated, causing the affected set to expand.
The procedure stops when the restricted homomorphism ceases to be giant or when no elements outside the window remain affected.The first case yields a non-fullness certificate; the second yields a fullness certificate contained in the global automorphism group.
Strong Luks reduction recomputes the relevant subgroup using at most n · k! String Isomorphism instances on windows of size at most n/k.

11 Effect of discovery of canonical structures

Canonical structures produced by group-theoretic and combinatorial partitioning align the input strings and reduce the group action. The resulting recursive cases either shrink the problem substantially or expose structured symmetry such as equipartitions and Johnson schemes.

Canonical structures: The algorithm constructs canonical colorings of Γ, sometimes augmented by an equipartition or Johnson scheme on a color class.
Alignment: Alignment compares the canonical structures of x and y, rejecting when they are not Gϕ-isomorphic and otherwise producing a shifted string and reduced group.
Reduction: A dominant color class larger than m/2 triggers recursive processing through a window associated with that class.Equipartitions replace the class by their blocks, while Johnson schemes induce a reduced action on a smaller set.
Complexity: The chain-rule analysis yields recursive costs involving T(n/3) and T(2n/3), with quasipolynomial overhead q(m).

12 The Master Algorithm

The master algorithm first reduces to Johnson-action cases, then applies canonical-structure routines, alignment, and recursive reductions according to the group’s transitivity and block structure.

Recursive processing: Returned color partitions restart the recursion, structured outputs advance the procedure, and rejection terminates the corresponding branch.
Johnson reduction: The master procedure begins with Luks reductions to a Johnson action and sets a polylogarithmic threshold ℓ = (log n)3.
Johnson reduction: When the Johnson parameter is small, strong Luks reduction handles the kernel by brute force; otherwise the algorithm constructs a giant representation and standard blocks.
Case analysis: Primitive cases with t = 1 are solved directly, while larger-transitivity cases are converted into edge-colored hypergraphs and canonical relational structures.
Recursive processing: The algorithm applies Procedure Align to canonical equipartitions or Johnson schemes, while imprimitive groups invoke AggregateCertificates and LocalCertificates.

13 Concluding remarks

The concluding discussion reduces reliance on classification results, explains why the quasipolynomial bound is significant for GI’s complexity status, and identifies unresolved barriers to polynomial time.

Classification dependence: The stated analysis still depends on the Classification of Finite Simple Groups through Cameron’s classification and Schreier’s Hypothesis.
Classification dependence: A further UPCC Split-or-Johnson application and older group theory remove the need for Cameron’s classification result in the analysis.
Group-theoretic reductions: Wielandt’s theorem bounds the transitivity degree of a doubly transitive non-giant group by t < 3 ln k, enabling individualization and block reduction.
Complexity significance: Quasipolynomial GI implies that GI is not NP-complete unless all of NP has quasipolynomial-time algorithms.
Open problems: Whether GI is in P remains open, and Group Isomorphism is still not known to be solvable in polynomial time despite a quasipolynomial bound.
Open problems: String Isomorphism for GL(k,p) on n = p^k points remains a challenge, including whether it can be solved in p^o(k2) or polynomial time.