Graph canonization

<h2 id="computational-complexity">Computational complexity</h2>

Unsolved problem in computer science:
Is graph canonization polynomial time equivalent to the graph isomorphism problem?
<a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">(more unsolved problems in computer science)</a>

The graph isomorphism problem is the <a href="/facts/Computational_problem/jQ7bYUVh">computational problem</a> of determining whether two finite <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graphs</a> are <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a>.
Clearly, the graph canonization problem is at least as <a href="/facts/Computational_complexity_theory/etHuVF3U">computationally hard</a> as the <a href="/facts/Graph_isomorphism_problem/Buhk3qsS">graph isomorphism problem</a>. In fact, graph isomorphism is even <a href="/facts/AC0/UGJ79CeY">AC0</a>-<a href="/facts/Reducible_(complexity)/IVWF7a1c">reducible</a> to graph canonization. However, it is still an open question whether the two problems are <a href="/facts/Polynomial_time_equivalent/bBvfFxyM">polynomial time equivalent</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
In 2019, <a href="/facts/L%25C3%25A1szl%25C3%25B3_Babai/6yflmWJv">László Babai</a> announced a <a href="/facts/Quasi-polynomial_time/77T62gmf">quasi-polynomial time</a> algorithm for graph canonization, that is, one with running time 
 
 
 
 
 2
 
 O
 (
 (
 log
 ⁡
 n
 
 )
 
 c
 
 
 )
 
 
 
 
 {\displaystyle 2^{O((\log n)^{c})}}
 
 for some fixed 
 
 
 
 c
 >
 0
 
 
 {\displaystyle c>0}
 
.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> While the existence of (deterministic) polynomial algorithms for graph isomorphism is still an open problem in <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, in 1977 <a href="/facts/L%25C3%25A1szl%25C3%25B3_Babai/6yflmWJv">László Babai</a> reported that with probability at least 1 − exp(−O(n)), a simple vertex classification algorithm produces a canonical labeling of a graph chosen uniformly at random from the set of all n-vertex graphs after only two refinement steps. Small modifications and an added <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> step produce canonical labeling of such uniformly-chosen random graphs in linear expected time. This result sheds some light on the fact why many reported graph isomorphism algorithms behave well in practice.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> This was an important breakthrough in <a href="/facts/Probabilistic_complexity_theory/Fngl1zgk">probabilistic complexity theory</a> which became widely known in its manuscript form and which was still cited as an "unpublished manuscript" long after it was reported at a symposium.
A commonly known canonical form is the <a href="/facts/Lexicographical_order/xQANy8Br">lexicographically smallest</a> graph within the <a href="/facts/Isomorphism_class/wDUgsJQ8">isomorphism class</a>, which is the graph of the class with lexicographically smallest <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> considered as a linear string.
However, the computation of the lexicographically smallest graph is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>. <a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
For trees, a concise polynomial canonization algorithm requiring O(n) space is presented by Read (1972).<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Begin by labeling each vertex with the string 01. Iteratively for each non-leaf x remove the leading 0 and trailing 1 from x's label; then sort x's label along with the labels of all adjacent leaves in lexicographic order. Concatenate these sorted labels, add back a leading 0 and trailing 1, make this the new label of x, and delete the adjacent leaves. If there are two vertices remaining, concatenate their labels in lexicographic order.

<h2 id="applications">Applications</h2>
Graph canonization is the essence of many graph isomorphism algorithms. One of the leading tools is Nauty.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
A common application of graph canonization is in graphical <a href="/facts/Data_mining/AH53q5ac">data mining</a>, in particular in <a href="/facts/Chemical_database/AvlsG1nv">chemical database</a> applications.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
A number of <a href="/facts/Identifier/pPaQPLhj">identifiers</a> for <a href="/facts/Chemical_substance/EWcXU41d">chemical substances</a>, such as <a href="/facts/SMILES/NUzV73WA">SMILES</a> and <a href="/facts/InChI/6yR96JYR">InChI</a> use canonicalization steps in their computation, which is essentially the canonicalization of the graph which represents the molecule.
<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
These identifiers are designed to provide a standard (and sometimes human-readable) way to encode molecular information and to facilitate the search for such information in databases and on the web.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Arvind, Vikraman; Das, Bireswar; Köbler, Johannes (2008), "A logspace algorithm for partial 2-tree canonization", Computer Science – Theory and Applications: Third International Computer Science Symposium in Russia, CSR 2008 Moscow, Russia, June 7-12, 2008, Proceedings, Lecture Notes in Comput. Sci., vol. 5010, Springer, Berlin, pp. 40–51, doi:10.1007/978-3-540-79709-8_8, ISBN 978-3-540-79708-1, MR 2475148. <a href="978-3-540-79708-1" target="_blank">978-3-540-79708-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Arvind, V.; Das, Bireswar; Köbler, Johannes (2007), "The space complexity of k-tree isomorphism", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, Lecture Notes in Comput. Sci., vol. 4835, Springer, Berlin, pp. 822–833, doi:10.1007/978-3-540-77120-3_71, ISBN 978-3-540-77118-0, MR 2472661. <a href="978-3-540-77118-0" target="_blank">978-3-540-77118-0</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gurevich, Yuri (1997), "From invariants to canonization" (PDF), Bulletin of the European Association for Theoretical Computer Science (63): 115–119, MR 1621595. <a href="http://research.microsoft.com/en-us/um/people/gurevich/opera/131.pdf" target="_blank">http://research.microsoft.com/en-us/um/people/gurevich/opera/131.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Babai, László; Luks, Eugene (1983), "Canonical labeling of graphs", Proc. 15th ACM Symposium on Theory of Computing, pp. 171–183, doi:10.1145/800061.808746, ISBN 0-89791-099-0. <a href="0-89791-099-0" target="_blank">0-89791-099-0</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Arvind, V.; Das, Bireswar; Köbler, Johannes (2007), "The space complexity of k-tree isomorphism", Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, Lecture Notes in Comput. Sci., vol. 4835, Springer, Berlin, pp. 822–833, doi:10.1007/978-3-540-77120-3_71, ISBN 978-3-540-77118-0, MR 2472661. <a href="978-3-540-77118-0" target="_blank">978-3-540-77118-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Babai, László (June 23, 2019), Canonical Form for Graphs in Quasipolynomial Time <a href="https://par.nsf.gov/servlets/purl/10179675" target="_blank">https://par.nsf.gov/servlets/purl/10179675</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Babai, László (1977), On the Isomorphism Problem, unpublished manuscript. <a href="/wiki/L%C3%A1szl%C3%B3_Babai" target="_blank">/wiki/L%C3%A1szl%C3%B3_Babai</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Babai, László; Kucera, L. (1979), "Canonical labeling of graphs in linear average time", Proc. 20th Annual IEEE Symposium on Foundations of Computer Science, pp. 39–46, doi:10.1109/SFCS.1979.8, S2CID 14697933. <a href="/wiki/L%C3%A1szl%C3%B3_Babai" target="_blank">/wiki/L%C3%A1szl%C3%B3_Babai</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Babai, László; Luks, E. (1983), "Canonical labeling of graphs", Proc. 15th ACM Symposium on Theory of Computing, pp. 171–183 <a href="/wiki/L%C3%A1szl%C3%B3_Babai" target="_blank">/wiki/L%C3%A1szl%C3%B3_Babai</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New York, pp. 153–182, MR 0344150. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">McKay, Brendan D.; Piperno, Adolfo (2014), "Journal of Symbolic Computation", Practical graph isomorphism, II, vol. 60, pp. 94–112, arXiv:1301.1493, doi:10.1016/j.jsc.2013.09.003, ISSN 0747-7171, S2CID 17930927. <a href="http://pallini.di.uniroma1.it" target="_blank">http://pallini.di.uniroma1.it</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Cook, Diane J.; Holder, Lawrence B. (2007), "6.2.1. Canonical Labeling", Mining Graph Data, John Wiley & Sons, pp. 120–122, ISBN 978-0-470-07303-2. <a href="978-0-470-07303-2" target="_blank">978-0-470-07303-2</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Weininger, David; Weininger, Arthur; Weininger, Joseph L. (May 1989). "SMILES. 2. Algorithm for generation of unique SMILES notation". Journal of Chemical Information and Modeling. 29 (2): 97–101. doi:10.1021/ci00062a008. S2CID 6621315. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Kelley, Brian (May 2003). "Graph Canonicalization". Dr. Dobb's Journal. <a href="http://www.drdobbs.com/graph-canonicalization/184405341" target="_blank">http://www.drdobbs.com/graph-canonicalization/184405341</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Scheider, Nadine; Sayle, Roger A.; Landrum, Gregory A. (October 2015). "Get Your Atoms in Order — An Open-Source Implementation of a Novel and Robust Molecular Canonicalization Algorithm". Journal of Chemical Information and Modeling. 55 (10): 2111–2120. doi:10.1021/acs.jcim.5b00543. PMID 26441310. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
</ol>

Graph canonization open-in-new

Graph canonization