László Babai
ABSTRACT
We show that the Graph Isomorphism (GI) problem and the more general problems of String Isomorphism (SI) andCoset Intersection (CI) can be solved in quasipolynomial(exp((logn)O(1))) time. The best previous bound for GI was exp(O( √n log n)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp(O~(√ n)), where n is the size of the permutation domain (Babai, 1983). Following the approach of Luks’s seminal 1980/82 paper, the problem we actually address is SI. This problem takes two strings of length n and a permutation group G of degree n (the “ambient group”) as input (G is given by a list of generators) and asks whether or not one of the strings can be transformed into the other by some element of G. Luks’s divide-and-conquer algorithm for SI proceeds by recursion on the ambient group. We build on Luks’s framework and attack the obstructions to efficient Luks recurrence via an interplay between local and global symmetry. We construct group theoretic “local certificates” to certify the presence or absence of local symmetry, aggregate the negative certificates to canonical k-ary relations where k = O(log n), and employ combinatorial canonical partitioning techniques to split the k-ary relational structure for efficient divide-and- conquer. We show that in a well–defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. The central element of the algorithm is the “local certificates” routine which is based on a new group theoretic result, the “Unaffected stabilizers lemma,” that allows us to construct global automorphisms out of local information.
- {ArT} V. Arvind and Jacobo Torán: Isomorphism testing: Perspectives and open problems. Bull. EATCS 86, June 2005.Google Scholar
- {Ba08} László Babai: Coset intersection in moderately exponential time. Manuscript, 2008. http://people.cs.uchicago.edu/∼laci/int.pdf {Ba15} László Babai: Graph Isomorphism in quasipolynomial time. arXiv:1512.03547, 2015.Google Scholar
- (Reprinted 1957, Paris, Albert Blanchard) {Jor2} Camille Jordan: Nouvelles recherches sur la limite de transivité des groupes qui ne contiennent pas le groupe alterné. J. de Math. Pures et Appliquées 1 (1895), 35–60. {KlL} Peter Kleidman and Martin Liebeck: The Subgroup Structure of the Finite Classical Groups. London Math. Soc. Lecture Note Ser. Vol. 129, Cambridge Univ. Press, 1990.Google Scholar
- {Mi} Takunari Miyazaki: Luks’s reduction of Graph isomorphism to code equivalence. Comment on The Math Forum, Sep. 29, 1996. http://mathforum.org/kb/thread.jspa? forumID=253&threadID=561418& messageID=1681072#1681072 {NeS} Daniel Neuen, Pascal Schweitzer: Iterated CFI graphs. Personal communication by P. S., 2015.Google Scholar
- {OWWZ} Ryan O’Donnell, John Wright, Chenggang Wu, Yuan Zhou: Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs. In: Proc. 25th ACM–SIAM Symp. Disr. Alg. (SODA’14), 2014, pp. 1659–1677. Google ScholarDigital Library
- {Pi} Adolfo Piperno: Search Space Contraction in Canonical Labeling of Graphs. arXiv:0804.4881, 2008, v2 2011.Google Scholar
- {Py} László Pyber: On the orders of doubly transitive permutation groups, elementary estimates. J. Combinatorial Theory, Ser A 62(2) (1993) 361–366. {Py} László Pyber: Personal comunication, 2016. Google ScholarDigital Library
- {Ro} Joseph Rotman: An Introduction to the Theory of Groups. 4th ed., Springer, 1995.Google ScholarCross Ref
- {WeL} Boris Weisfeiler, Andrei A. Leman: A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya 9 (1968) 12–16. {Wi34} Helmut Wielandt: Abschätzungen für den Grad einer Permutationsgruppe von vorgeschriebenem Transitivitätsgrad. Dissertation, Berlin, 1934. Schriften Math. Seminars Inst. Angew. Math. Univ. Berlin 2 (1934) 151–174. {Wi60} Helmut Wielandt: Über den Transitivitätsgrad von Permutationsgruppen. Math. Z. 74 (1960) 297–298. {Wi3} Helmut Wielandt: Finite Permutation Groups. Acad. Press, New York 1964.Google Scholar
Index Terms
- Graph isomorphism in quasipolynomial time [extended abstract]
Recommendations
Reductions to Graph Isomorphism
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer ScienceAbstractWe show that several reducibility notions coincide when applied to the Graph Isomorphism (GI) problem. In particular we show that if a set is many-one logspace reducible to GI, then it is in fact many-one AC0 reducible to GI. For the case of ...
Reductions to Graph Isomorphism
Special Section: Algorithmic Game Theory; Guest Editors: Burkhard Monien and Ulf-Peter SchroederWe show that several reducibility notions coincide when applied to the Graph Isomorphism (GI) problem. In particular we show that if a set is many-one logspace reducible to GI, then it is in fact many-one $\textsf{AC}^{0}$reducible to GI. For the case ...
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Traditional hardness versus randomness results focus on time-efficient randomized decision procedures. We generalize these trade-offs to a much wider class of randomized processes. We work out various applications, most notably to derandomizing Arthur-...
Comments