Canonical labeling of graphs

By László Babai, Eugene M. Luks. 1983

We announce an algebraic approach to the problem of assigning canonical forms to graphs. We compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(n½ + &ogr;(1)),time for general graphs, in subexponential, nlog n, time for tournaments and for 2-(&ngr;,&kgr;,&lgr;) block designs with &kgr;,&lgr; bounded and nlog log n time for &lgr;-planes (symmetric designs) with &lgr; bounded. We prove some related problems NP-hard and indicate some open problems.

Subfields: Graph Learning, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Graph Learning

In Algorithms & Complexity

Citations in the corpus

The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “However the best current GI algorithm for general graphs has an upper bound of O(e √ nlogn) [8, 32, 6].”
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (2013, background): “For example, Babai and Luks’s [1,3] O(2 √ n )-algorithm — this is still”
Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks (1995, background): “So the canonization problem for pairs is reduced to that for cellular algebras on the set V = [n] with respect to the group G in sense of [3].”
An optimal lower bound on the number of variables for graph identification (1989, methodology): “For tournaments, the isomorphism problems of primitive and arbitrary coherent configurations are polynomial time equivalent [11].”
Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, background): “Currently the best asymptotic running time bound for canonical labeling of graphs remains quasi-exponential in the number of vertices [4] [6].”
Graph isomorphism is in SPP (2002, methodology): “There is an O(n) algorithm for Tournament Isomorphism by giving a canonization procedure for tournements [3].”
Logical complexity of graphs: a survey (2010, methodology): “The best known algorithm (Babai, Luks, and Zemlyachenko [9]) takes time 2O( √ n logn), where n denotes the number of vertices in the input graphs.”
Polymorphic Worm Detection Using Structural Information of Executables (2005, background): “This problem is known as canonical graph labeling [1].”
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem (2003, background): “This is the same complexity class as a known classical algorithm for the graph isomorphism or automorphism problem [3], which is the original motivation for the symmetric hidden su bgroup problem (SHSP).”
The complexity of McKay's canonical labeling algorithm (1995, methodology): “We begin with deﬁnitions and describe fundamentals of the naive vertex classi-ﬁcation method (see [1], [2], [3]).”
An optimal lower bound on the number of variables for graph identification (1992, methodology): “[5]). His bound is exp(n 1-c) for some positive constant c. This has subsequently been improved by Babai and Luks [ 11 ] to exp(nl/2+~”