Canonical labeling of graphs

ABSTRACT

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.

REFERENCES

• 1: L. Babai, Monte-Carlo algorithms in graph isomorphism testing, preprint, Univ. Montréal (1979).
• 2: L. Babai, On the complexity of canonical labeling of strongly regular graphs, SIAM J. Comp. 9 (1980), 212-216.
• 3: László Babai, Moderately Exponential Bound for Graph Isomorphism, Proceedings of the 1981 International FCT-Conference on Fundamentals of Computation Theory, p.34-50, August 24-28, 1981
• 4: L. Babai, On the order of uniprimitive permutation groups, Ann. of Math 113 (1981), 553-568.
• 5: L. Babai, On the order of doubly transitive permutation groups, Inventiones Math 65, 473-484.
• 6: L. Babai, Permutation group intersection in exp(n½+&ogr;(1);) time, to appear.
• 7: L. Babai, P. Cameron, P. Pàlfy, On the orders of primitive groups with restricted nonabelian composition factors, J. Alg., 79 (1982), 161-168.
• 8: László Babai , D. Yu. Grigoryev , David M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.310-324, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802206]
• 9: A. Blass and Y. Gurevich, Equivalence relations, invariants and normal forms, to appear.
• 10: L. Babai, P. Klingsberg, E. Luks, Canonical labeling for vertex colored graphs, to appear.
• 11: P. Cameron, Strongly regular graphs, Selected Topics in Graph Theory, ed. L. Beineke, R. Wilson, Academic Press, (1979).
• 12: P. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), 1-22.
• 13: D. Corneil, Private communication.
• 14: D. Corneil and M. Golberg, On graph certificates, Congressus Num. 35 (1982), 181-190.
• 15: C. Colbourne and M. Colbourne, The complexity of combinatorial isomorphism problems, Proc. Can.-France Comb. Coll., Montreal (1979).
• 16: W. Feit and J. Thompson, Solvability of groups of odd order, Pac. J. Math. 13 (1983), 775-1029.
• 17: I. S. Filotti , Jack N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.236-243, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804671]
• 18: M. Furst, J. Hopcroft, E. Luks, Polynomial-time algorithms for permutation groups, 21st IEEE Symp. Found. Comp. Sci. (1980), 36-41.
• 19: Z. Galil, private communication.
• 20: Z. Galil, C. Hoffman, E. Luks, C. Schnorr, A. Weber, An O(n3log n) deterministic an O(n3) probabilistic isomorphism test for trivalent graphs, 23rd IEEE Symp. Found. Comp. Sci. (1982), 118-125.
• 21: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 22: Z. Hedrlin and P. Pultr, On full embeddings of categories of algebras, I11. J. Math. 10(1966), 392-406.
• 23: J. Hopcroft and R. Tarjan, Isomorphism of planar graphs (working paper), Complexity of Computer Computations, Plenum (1972), 131-152.
• 24: P. Klingsberg, E. Luks, Succinct certificates for a class of graphs, St. Joseph's Univ. preprint (1981) (See {BKL}).
• 25: R. Lipton, The beacon set approach to graph isomorphism, Yale Dept. Comp Sci. preprint #135 (1978).
• 26: E. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comp. Sys. Sci. 25 (1982), 42-65.
• 27: E. Luks, On the complexity of fixed valence graph isomorphism and the implications for general graph isomorphism, to appear.
• 28: A. Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM J. Comp, 10 (1980), 11-21.
• 29: R. Mathon, A note on the graph isomorphism counting problem, Inf. Proc. Let. 8 (1979), 131-132.
• 30: G. Miller, Graph isomorphism, general remarks, J. Comp. Sys. Sci., 18 (1979), 128-142.
• 31: Gary L. Miller, On the nlog n isomorphism technique (A Preliminary Report), Proceedings of the tenth annual ACM symposium on Theory of computing, p.51-58, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804331]
• 32: Gary Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.225-235, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804670]
• 33: G. Miller, Isomorphism of graphs which are pairwise k-separable, to appear.
• 34: G. Miller, private communication.
• 35: P. Pálfy, A polynomial bound for the orders of primitive solvable groups, J. Alg., (1982), 127-137.
• 36: H. Ryser, Combinatorial Mathematics, MAA 1963.
• 37: C. Schnorr and A. Weber, Constructing the automorphism group Aute(X) for trivalent graphs in time O(n3log n), Tech. Rep., U. Frankfurt (1981).
• 38: B. Weisfeiler, ed., On Construction and Identification of Graphs, Lecture Notes in Math 558, Springer, 1976.
• 39: V. Zemlyachenko, N. Kornienko, R. Tyshkevich, Graph isomorphism problem (Russian) The Theory of Computation I, Notes Sci. Sem LOMI 118 (1982).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

General Terms:
Theory