Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8" /> <meta http-equiv="X-UA-Compatible" content="IE=edge" /> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1" /> <meta name="csrf-token" content="pcrxQL2Ic6g13eVH5DFbIqyUtlwZksbQfuMxMRr5" /> <meta name="DC.Publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" /> <meta name="DC.Title" xml:lang="en" content="Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman" /> <meta name="DC.Creator.PersonalName" content="Levet, Michael" /> <meta name="DC.Creator.PersonalName" content="Rombach, Puck" /> <meta name="DC.Creator.PersonalName" content="Sieger, Nicholas" /> <meta name="DC.Subject" content="Graph Isomorphism" /> <meta name="DC.Subject" content="Weisfeiler-Leman" /> <meta name="DC.Subject" content="Rank-Width" /> <meta name="DC.Subject" content="Canonization" /> <meta name="DC.Subject" content="Descriptive Complexity" /> <meta name="DC.Subject" content="Circuit Complexity" /> <meta name="DC.Date.created" scheme="ISO8601" content="2024-05-31" /> <meta name="DC.Date.issued" scheme="ISO8601" content="2024-05-31" /> <meta name="DC.Date.modified" scheme="ISO8601" content="2024-05-31" /> <meta name="DC.Type" content="InProceedings" /> <meta name="DC.Format" scheme="IMT" content="application/pdf" /> <meta name="DC.Identifier" scheme="urn:nbn:de" content="urn:nbn:de:0030-drops-200724" /> <meta name="DC.Identifier" scheme="DOI" content="10.4230/LIPIcs.SWAT.2024.32" /> <meta name="DC.Identifier" scheme="URL" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32" /> <meta name="DC.Source" content="19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)" /> <meta name="DC.Source.URI" content="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-294" /> <meta name="DC.Language" scheme="ISO639-1" content="en" /> <meta name="DC.Description" xml:lang="en" content="In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC². Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width ≤ 2k and height O(log n) (Courcelle & Kanté, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation. Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC¹. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC." /> <meta name="DC.Rights" scheme="DCTERMS.URI" content="https://creativecommons.org/licenses/by/4.0/legalcode" /> <meta name="citation_conference_title" content="19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)" /> <meta name="citation_doi" content="10.4230/LIPIcs.SWAT.2024.32" /> <meta name="citation_firstpage" content="32:1" /> <meta name="citation_lastpage" content="32:18" /> <meta name="citation_title" content="Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman" /> <meta name="citation_language" content="en" /> <meta name="citation_keyword" content="Graph Isomorphism" /> <meta name="citation_keyword" content="Weisfeiler-Leman" /> <meta name="citation_keyword" content="Rank-Width" /> <meta name="citation_keyword" content="Canonization" /> <meta name="citation_keyword" content="Descriptive Complexity" /> <meta name="citation_keyword" content="Circuit Complexity" /> <meta name="citation_author" content="Levet, Michael" /> <meta name="citation_author_institution" content="Department of Computer Science, College of Charleston, SC, USA" /> <meta name="citation_author" content="Rombach, Puck" /> <meta name="citation_author_institution" content="Department of Mathematics and Statistics, University of Vermont, Burlington, VT, USA" /> <meta name="citation_author" content="Sieger, Nicholas" /> <meta name="citation_author_institution" content="Department of Mathematics, University of California San Diego, La Jolla, CA, USA" /> <meta name="citation_date" content="2024" /> <meta name="citation_keyword" xml:lang="en" content="Graph Isomorphism" /> <meta name="citation_keyword" xml:lang="en" content="Weisfeiler-Leman" /> <meta name="citation_keyword" xml:lang="en" content="Rank-Width" /> <meta name="citation_keyword" xml:lang="en" content="Canonization" /> <meta name="citation_keyword" xml:lang="en" content="Descriptive Complexity" /> <meta name="citation_keyword" xml:lang="en" content="Circuit Complexity" /> <meta name="citation_pdf_url" content="https://drops.dagstuhl.de/storage/00lipics/lipics-vol294-swat2024/LIPIcs.SWAT.2024.32/LIPIcs.SWAT.2024.32.pdf" /> <meta name="citation_reference" content="V. Arvind and Piyush P. Kurur. Graph isomorphism is in SPP. Information and Computation, 204(5):835-852, 2006. URL: https://doi.org/10.1016/j.ic.2006.02.002." /> <meta name="citation_reference" content="L. Babai, E. Luks, and A. Seress. Permutation groups in NC. In STOC 1987, STOC '87, pages 409-420, New York, NY, USA, 1987. Association for Computing Machinery. URL: https://doi.org/10.1145/28395.28439." /> <meta name="citation_reference" content="László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In STOC'16 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684-697. ACM, New York, 2016. Preprint of full version at https://arxiv.org/abs/1512.03547v2. URL: https://doi.org/10.1145/2897518.2897542." /> <meta name="citation_reference" content="László Babai. Canonical form for graphs in quasipolynomial time: Preliminary report. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1237-1246, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316356." /> <meta name="citation_reference" content="Hans L. Bodlaender. NC-algorithms for graphs with small treewidth. In J. van Leeuwen, editor, Graph-Theoretic Concepts in Computer Science, pages 1-10, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-50728-0_32." /> <meta name="citation_reference" content="Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In R. K. Shyamasundar, editor, Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, volume 652 of Lecture Notes in Computer Science, pages 116-127. Springer, 1992. URL: https://doi.org/10.1007/3-540-56287-7_99." /> <meta name="citation_reference" content="Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. Originally appeared in SFCS '89. URL: https://doi.org/10.1007/BF01305232." /> <meta name="citation_reference" content="Bruno Courcelle and Mamadou Kanté. Graph operations characterizing rank-width and balanced graph expressions. In Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, pages 66-75, June 2007. URL: https://doi.org/10.1007/978-3-540-74839-7_7." /> <meta name="citation_reference" content="Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5." /> <meta name="citation_reference" content="Bireswar Das, Anirban Dasgupta, Murali Krishna Enduri, and I. Vinod Reddy. On nc algorithms for problems on bounded rank-width graphs. Information Processing Letters, 139:64-67, 2018. URL: https://doi.org/10.1016/j.ipl.2018.07.007." /> <meta name="citation_reference" content="Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. Information and Computation, 217:71-83, 2012. URL: https://doi.org/10.1016/j.ic.2012.05.003." /> <meta name="citation_reference" content="Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 203-214, 2009. URL: https://doi.org/10.1109/CCC.2009.16." /> <meta name="citation_reference" content="Heinz-Dieter Ebbinghaus, J. Flum, and W. Thomas. Mathematical Logic. Springer, 2 edition, 1994. URL: https://doi.org/10.1007/978-1-4757-2355-7." /> <meta name="citation_reference" content="Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 383-392, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591865." /> <meta name="citation_reference" content="Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. ACM Trans. Comput. Theory, 9(3), October 2017. URL: https://doi.org/10.1145/3132720." /> <meta name="citation_reference" content="Vyacheslav Futorny, Joshua A. Grochow, and Vladimir V. Sergeichuk. Wildness for tensors. Lin. Alg. Appl., 566:212-244, 2019. Preprint arXiv:1810.09219 [math.RT]. URL: https://doi.org/10.1016/j.laa.2018.12.022." /> <meta name="citation_reference" content="Joshua A. Grochow and Youming Qiao. Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. arXiv:1907.00309 [cs.CC], 2019. URL: https://doi.org/10.48550/arXiv.1907.00309." /> <meta name="citation_reference" content="Martin Grohe. Isomorphism testing for embeddable graphs through definability. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, pages 63-72, New York, NY, USA, 2000. Association for Computing Machinery. URL: https://doi.org/10.1145/335305.335313." /> <meta name="citation_reference" content="Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM, 59(5), November 2012. URL: https://doi.org/10.1145/2371656.2371662." /> <meta name="citation_reference" content="Martin Grohe and Sandra Kiefer. A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 117:1-117:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.117." /> <meta name="citation_reference" content="Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 134:1-134:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.134." /> <meta name="citation_reference" content="Martin Grohe and Daniel Neuen. Canonisation and definability for graphs of bounded rank width. ACM Trans. Comput. Log., 24(1):6:1-6:31, 2023. URL: https://doi.org/10.1145/3568025." /> <meta name="citation_reference" content="Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An improved isomorphism test for bounded-tree-width graphs. ACM Trans. Algorithms, 16(3), June 2020. URL: https://doi.org/10.1145/3382082." /> <meta name="citation_reference" content="Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded rank width. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1010-1029, 2015. URL: https://doi.org/10.1109/FOCS.2015.66." /> <meta name="citation_reference" content="Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 3-14. Springer, 2006. URL: https://doi.org/10.1007/11786986_2." /> <meta name="citation_reference" content="Lauri Hella. Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic, 43(3):235-271, 1989. URL: https://doi.org/10.1016/0168-0072(89)90070-5." /> <meta name="citation_reference" content="Lauri Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 1996. URL: https://doi.org/10.1006/inco.1996.0070." /> <meta name="citation_reference" content="Sang il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. URL: https://doi.org/10.1016/j.jctb.2005.10.006." /> <meta name="citation_reference" content="Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81. Springer New York, New York, NY, 1990. URL: https://doi.org/10.1007/978-1-4612-4478-3_5." /> <meta name="citation_reference" content="Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774." /> <meta name="citation_reference" content="Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The Weisfeiler-Leman dimension of planar graphs is at most 3. J. ACM, 66(6), November 2019. URL: https://doi.org/10.1145/3333003." /> <meta name="citation_reference" content="Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky. Interval graphs: Canonical representations in logspace. SIAM Journal on Computing, 40(5):1292-1315, 2011. URL: https://doi.org/10.1137/10080395X." /> <meta name="citation_reference" content="Johannes Köbler, Uwe Schöning, and Jacobo Torán. Graph isomorphism is low for PP. Comput. Complex., 2:301-330, 1992. URL: https://doi.org/10.1007/BF01200427." /> <meta name="citation_reference" content="Johannes Köbler and Oleg Verbitsky. From invariants to canonization in parallel. In Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, and Anatol Slissenko, editors, Computer Science - Theory and Applications, pages 216-227, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-540-79709-8_23." /> <meta name="citation_reference" content="Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. On the isomorphism problem for helly circular-arc graphs. Information and Computation, 247:266-277, 2016. URL: https://doi.org/10.1016/j.ic.2016.01.006." /> <meta name="citation_reference" content="Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, January 1975. URL: https://doi.org/10.1145/321864.321877." /> <meta name="citation_reference" content="Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. URL: https://doi.org/10.1007/978-3-662-07003-1_1." /> <meta name="citation_reference" content="Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM Journal on Computing, 46(1):161-189, 2017. URL: https://doi.org/10.1137/140999980." /> <meta name="citation_reference" content="Rudolf Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131-136, 1979. URL: https://doi.org/10.1016/0020-0190(79)90004-8." /> <meta name="citation_reference" content="Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualization-refinement algorithms for graph isomorphism. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 138-150. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188900." /> <meta name="citation_reference" content="Sang-il Oum. Rank-width is less than or equal to branch-width. Journal of Graph Theory, 57(3):239-244, 2008. URL: https://doi.org/10.1002/jgt.20280." /> <meta name="citation_reference" content="Uwe Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312-323, 1988. URL: https://doi.org/10.1016/0022-0000(88)90010-4." /> <meta name="citation_reference" content="Thomas Thierauf and Fabian Wagner. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory Comput. Syst., 47(3):655-673, 2010. URL: https://doi.org/10.1007/S00224-009-9188-4." /> <meta name="citation_reference" content="Jacobo Torán. On the hardness of graph isomorphism. SIAM J. Comput., 33(5):1093-1108, 2004. URL: https://doi.org/10.1137/S009753970241096X." /> <meta name="citation_reference" content="Oleg Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. In STACS 2007, pages 682-693, Berlin, Heidelberg, 2007. Springer-Verlag. URL: https://doi.org/10.5555/1763424.1763505." /> <meta name="citation_reference" content="Fabian Wagner. Graphs of bounded treewidth can be canonized in AC¹. In Proceedings of the 6th International Conference on Computer Science: Theory and Applications, CSR'11, pages 209-222, Berlin, Heidelberg, 2011. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-20712-9_16." /> <link rel="canonical" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32" /> <script type="application/json+ld"> {"@context":"https:\/\/schema.org\/","@type":"WebPage","mainEntity":{"@type":"ScholarlyArticle","@id":"#article20163","name":"Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman","abstract":"In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC\u00b2. Our approach builds on the framework of K\u00f6bler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width \u2264 2k and height O(log n) (Courcelle & Kant\u00e9, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation.\r\nFurthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC\u00b9. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC.","keywords":["Graph Isomorphism","Weisfeiler-Leman","Rank-Width","Canonization","Descriptive Complexity","Circuit Complexity"],"author":[{"@type":"Person","name":"Levet, Michael","givenName":"Michael","familyName":"Levet","email":"mailto:levetm@cofc.edu","affiliation":"Department of Computer Science, College of Charleston, SC, USA","funding":"Partially supported by J. A. Grochow\u2019s NSF award CISE-2047756 and the University of Colorado Boulder, Department of Computer Science Summer Research Fellowship."},{"@type":"Person","name":"Rombach, Puck","givenName":"Puck","familyName":"Rombach","email":"mailto:Puck.Rombach@uvm.edu","affiliation":"Department of Mathematics and Statistics, University of Vermont, Burlington, VT, USA"},{"@type":"Person","name":"Sieger, Nicholas","givenName":"Nicholas","familyName":"Sieger","email":"mailto:nsieger@ucsd.edu","affiliation":"Department of Mathematics, University of California San Diego, La Jolla, CA, USA"}],"position":32,"pageStart":"32:1","pageEnd":"32:18","dateCreated":"2024-05-31","datePublished":"2024-05-31","isAccessibleForFree":true,"license":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode","copyrightHolder":[{"@type":"Person","name":"Levet, Michael","givenName":"Michael","familyName":"Levet","email":"mailto:levetm@cofc.edu","affiliation":"Department of Computer Science, College of Charleston, SC, USA","funding":"Partially supported by J. A. Grochow\u2019s NSF award CISE-2047756 and the University of Colorado Boulder, Department of Computer Science Summer Research Fellowship."},{"@type":"Person","name":"Rombach, Puck","givenName":"Puck","familyName":"Rombach","email":"mailto:Puck.Rombach@uvm.edu","affiliation":"Department of Mathematics and Statistics, University of Vermont, Burlington, VT, USA"},{"@type":"Person","name":"Sieger, Nicholas","givenName":"Nicholas","familyName":"Sieger","email":"mailto:nsieger@ucsd.edu","affiliation":"Department of Mathematics, University of California San Diego, La Jolla, CA, USA"}],"copyrightYear":"2024","accessMode":"textual","accessModeSufficient":"textual","creativeWorkStatus":"Published","inLanguage":"en-US","sameAs":"https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2024.32","funding":"This work was completed in part at the 2022 Graduate Research Workshop in Combinatorics, which was supported in part by NSF grant #1953985 and a generous award from the Combinatorics Foundation.","publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","citation":["https:\/\/doi.org\/10.1016\/j.ic.2006.02.002","https:\/\/doi.org\/10.1145\/28395.28439","https:\/\/doi.org\/10.1145\/2897518.2897542","https:\/\/doi.org\/10.1145\/3313276.3316356","https:\/\/doi.org\/10.1007\/3-540-50728-0_32","https:\/\/doi.org\/10.1007\/3-540-56287-7_99","https:\/\/doi.org\/10.1007\/BF01305232","https:\/\/doi.org\/10.1007\/978-3-540-74839-7_7","https:\/\/doi.org\/10.1016\/S0166-218X(99)00184-5","https:\/\/doi.org\/10.1016\/j.ipl.2018.07.007","https:\/\/doi.org\/10.1016\/j.ic.2012.05.003","https:\/\/doi.org\/10.1109\/CCC.2009.16","https:\/\/doi.org\/10.1007\/978-1-4757-2355-7","https:\/\/doi.org\/10.1145\/2591796.2591865","https:\/\/doi.org\/10.1145\/3132720","https:\/\/doi.org\/10.1016\/j.laa.2018.12.022","https:\/\/doi.org\/10.48550\/arXiv.1907.00309","https:\/\/doi.org\/10.1145\/335305.335313","https:\/\/doi.org\/10.1145\/2371656.2371662","https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.117","https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.134","https:\/\/doi.org\/10.1145\/3568025","https:\/\/doi.org\/10.1145\/3382082","https:\/\/doi.org\/10.1109\/FOCS.2015.66","https:\/\/doi.org\/10.1007\/11786986_2","https:\/\/doi.org\/10.1016\/0168-0072(89)90070-5","https:\/\/doi.org\/10.1006\/inco.1996.0070","https:\/\/doi.org\/10.1016\/j.jctb.2005.10.006","https:\/\/doi.org\/10.1007\/978-1-4612-4478-3_5","https:\/\/doi.org\/10.1006\/jcss.2001.1774","https:\/\/doi.org\/10.1145\/3333003","https:\/\/doi.org\/10.1137\/10080395X","https:\/\/doi.org\/10.1007\/BF01200427","https:\/\/doi.org\/10.1007\/978-3-540-79709-8_23","https:\/\/doi.org\/10.1016\/j.ic.2016.01.006","https:\/\/doi.org\/10.1145\/321864.321877","https:\/\/doi.org\/10.1007\/978-3-662-07003-1_1","https:\/\/doi.org\/10.1137\/140999980","https:\/\/doi.org\/10.1016\/0020-0190(79)90004-8","https:\/\/doi.org\/10.1145\/3188745.3188900","https:\/\/doi.org\/10.1002\/jgt.20280","https:\/\/doi.org\/10.1016\/0022-0000(88)90010-4","https:\/\/doi.org\/10.1007\/S00224-009-9188-4","https:\/\/doi.org\/10.1137\/S009753970241096X","https:\/\/doi.org\/10.5555\/1763424.1763505","https:\/\/doi.org\/10.1007\/978-3-642-20712-9_16"],"isPartOf":{"@type":"PublicationVolume","@id":"#volume20129","volumeNumber":294,"name":"19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)","dateCreated":"2024-05-31","datePublished":"2024-05-31","editor":{"@type":"Person","name":"Bodlaender, Hans L.","givenName":"Hans L.","familyName":"Bodlaender","email":"mailto:h.l.bodlaender@uu.nl","sameAs":"https:\/\/orcid.org\/0000-0002-9297-3330","affiliation":"Utrecht University, The Netherlands"},"isAccessibleForFree":true,"publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","hasPart":"#article20163","isPartOf":{"@type":"Periodical","@id":"#series116","name":"Leibniz International Proceedings in Informatics","issn":"1868-8969","isAccessibleForFree":true,"publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","hasPart":"#volume20129"}}}} </script> <title>Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico" /> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2024-10-22" /> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height=62" alt="Schloss Dagstuhl - LZI - Logo" /> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item"> <a class="nav-link" href="https://drops.dagstuhl.de/docs/about" id="navbarAbout"> <i class="bi bi-info-circle large-icon"></i><span class="nav-text-about-drops"> About DROPS</span> </a> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="pcrxQL2Ic6g13eVH5DFbIqyUtlwZksbQfuMxMRr5" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2024-10-22" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="document-details"> <section class="mt-3 mb-5 title"> <div class="entity-type document"> <div class="row"> <div class="col-lg-3 entity-type-name"> <i class="bi bi-file-earmark"></i> Document <img src="https://drops.dagstuhl.de/images/open-access-logo.png" width="80px" alt="Open Access Logo" style="transform: translate(1em, -0.2em);"/> </div> <div class="col-lg-9"> <input id="doi" type="text" style="position: fixed; top: -50vh" value="https://doi.org/10.4230/LIPIcs.SWAT.2024.32"/> <div class="sharing-section"> <span class="permalink"> <span> <code><span class="hide-mobile">https://doi.org/</span>10.4230/LIPIcs.SWAT.2024.32</code> <span class="btn btn-clipboard copy-to-clipboard" title="Copy to clipboard" data-selector="doi"> <i class="bi bi-clipboard" aria-hidden="true"></i> <i class="bi bi-check -hidden" aria-hidden="true"></i> </span> </span> </span> <span class="sharing-buttons"> <a class="btn sharing-btn facebook" href="https://facebook.com/sharer/sharer.php?u=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SWAT.2024.32" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-facebook"></i> </a> <a class="btn sharing-btn reddit" href="https://www.reddit.com/submit?url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SWAT.2024.32&title=Canonizing+Graphs+of+Bounded+Rank-Width+in+Parallel+via+Weisfeiler-Leman" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-reddit"></i> </a> <a class="btn sharing-btn twitter" href="https://twitter.com/intent/tweet/?text=Canonizing+Graphs+of+Bounded+Rank-Width+in+Parallel+via+Weisfeiler-Leman&url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SWAT.2024.32" target="_blank" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-twitter-x" viewBox="0 0 16 16"> <path d="M12.6.75h2.454l-5.36 6.142L16 15.25h-4.937l-3.867-5.07-4.425 5.07H.316l5.733-6.57L0 .75h5.063l3.495 4.633L12.601.75Zm-.86 13.028h1.36L4.323 2.145H2.865l8.875 11.633Z"/> </svg> </a> <a class="btn sharing-btn email" href="mailto:?subject=Canonizing+Graphs+of+Bounded+Rank-Width+in+Parallel+via+Weisfeiler-Leman&body=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.SWAT.2024.32" target="_self" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="currentColor"> <path d="M22 4H2C.9 4 0 4.9 0 6v12c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zM7.25 14.43l-3.5 2c-.08.05-.17.07-.25.07-.17 0-.34-.1-.43-.25-.14-.24-.06-.55.18-.68l3.5-2c.24-.14.55-.06.68.18.14.24.06.55-.18.68zm4.75.07c-.1 0-.2-.03-.27-.08l-8.5-5.5c-.23-.15-.3-.46-.15-.7.15-.22.46-.3.7-.14L12 13.4l8.23-5.32c.23-.15.54-.08.7.15.14.23.07.54-.16.7l-8.5 5.5c-.08.04-.17.07-.27.07zm8.93 1.75c-.1.16-.26.25-.43.25-.08 0-.17-.02-.25-.07l-3.5-2c-.24-.13-.32-.44-.18-.68s.44-.32.68-.18l3.5 2c.24.13.32.44.18.68z"/> </svg> </a> </span> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32/metadata/bibtex"> Export BibTeX </a> </li> </ul> </span> </span> </div> </div> </div> </div> <hr/> <h1>Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman</h1> <h3 class="mt-2 authors"> Authors <a href="#author-details" style="font-size: 0.8em; padding-right: 1em"><i class="bi bi-info-circle"></i></a> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Levet, Michael" class="name">Michael Levet</a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Rombach, Puck" class="name">Puck Rombach</a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Sieger, Nicholas" class="name">Nicholas Sieger</a> </span> </h3> <hr/> <ul class="mt-4"> <li> <span style="margin-right: 10px; ">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-book-half"></i> Volume: </span> <a href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-294">19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) </a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/LIPIcs">Leibniz International Proceedings in Informatics (LIPIcs)</a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/SWAT">Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)</a> </li> <li class="mt-2">License:   <a href="https://creativecommons.org/licenses/by/4.0/legalcode"> <img class="license-logo" src="https://drops.dagstuhl.de/images/cc-by.png" alt="CC-BY Logo"> Creative Commons Attribution 4.0 International license </a> </li> <li>Publication Date: 2024-05-31 </li> </ul> <hr/> </section> <a class="fixed-pdf-button" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol294-swat2024/LIPIcs.SWAT.2024.32/LIPIcs.SWAT.2024.32.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> PDF </a> <div class="row mt-2"> <div class="col-lg-4 mt-2"> <section class="thumbnail"> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol294-swat2024/LIPIcs.SWAT.2024.32/LIPIcs.SWAT.2024.32.pdf"><img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol294-swat2024/thumbnails/LIPIcs.SWAT.2024.32/LIPIcs.SWAT.2024.32.png" alt="Thumbnail PDF" /></a> </section> <section class="files mt-5"> <h2>File</h2> <div class="content"> <div> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol294-swat2024/LIPIcs.SWAT.2024.32/LIPIcs.SWAT.2024.32.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> LIPIcs.SWAT.2024.32.pdf</a> <ul> <li>Filesize: 0.81 MB</li> <li>18 pages</li> </ul> </div> </div> </section> <section class="identifiers mt-3"> <h2>Document Identifiers</h2> <div class="content"> <ul> <li><b>DOI:</b> <a href="https://doi.org/10.4230/LIPIcs.SWAT.2024.32">10.4230/LIPIcs.SWAT.2024.32</a></li> <li><b>URN:</b> <a href="https://nbn-resolving.org/process-urn-form?identifier=urn:nbn:de:0030-drops-200724&verb=FULL">urn:nbn:de:0030-drops-200724</a></li> </ul> </div> </section> <section class="authors mt-3" id="author-details"> <h2>Author Details</h2> <div class="author person-details"> <div> <span class="name"><b>Michael Levet</b></span> <a href="mailto:levetm@cofc.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Levet, Michael"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Computer Science, College of Charleston, SC, USA</li> </ul> </div> <div class="author person-details"> <div> <span class="name"><b>Puck Rombach</b></span> <a href="mailto:Puck.Rombach@uvm.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Rombach, Puck"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Mathematics and Statistics, University of Vermont, Burlington, VT, USA</li> </ul> </div> <div class="author person-details"> <div> <span class="name"><b>Nicholas Sieger</b></span> <a href="mailto:nsieger@ucsd.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Sieger, Nicholas"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Department of Mathematics, University of California San Diego, La Jolla, CA, USA</li> </ul> </div> </section> <section class="related-version mt-3"> <h2>Funding</h2> <div class="content"> This work was completed in part at the 2022 Graduate Research Workshop in Combinatorics, which was supported in part by NSF grant #1953985 and a generous award from the Combinatorics Foundation. <ul> <li><b>Levet, Michael</b>: Partially supported by J. A. Grochow’s NSF award CISE-2047756 and the University of Colorado Boulder, Department of Computer Science Summer Research Fellowship.</li> </ul> </div> </section> </div> <div class="col-lg-8 mt-2"> <section class="cite-as mt-3"> <h2>Cite As<span class="btn btn-primary btn-xs" style="float: right" data-bs-toggle="modal" data-bs-target="#bibtex-modal">Get BibTex</span></h2> <div class="content"> Michael Levet, Puck Rombach, and Nicholas Sieger. Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)<br> <a href="https://doi.org/10.4230/LIPIcs.SWAT.2024.32" style="word-break: break-all">https://doi.org/10.4230/LIPIcs.SWAT.2024.32</a> </div> <div class="modal fade" id="bibtex-modal" tabindex="-1" aria-labelledby="bibtexModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content"> <div class="modal-header"> <h5 class="modal-title" id="bibtexModalLabel">BibTex</h5> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <pre class="bibtex">@InProceedings{levet_et_al:LIPIcs.SWAT.2024.32, author = {Levet, Michael and Rombach, Puck and Sieger, Nicholas}, title = {{Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32}, URN = {urn:nbn:de:0030-drops-200724}, doi = {10.4230/LIPIcs.SWAT.2024.32}, annote = {Keywords: Graph Isomorphism, Weisfeiler-Leman, Rank-Width, Canonization, Descriptive Complexity, Circuit Complexity} }</pre> <div style="overflow: hidden"> <textarea style="position: absolute; top: -400vh" id="bibtex-input">@InProceedings{levet_et_al:LIPIcs.SWAT.2024.32, author = {Levet, Michael and Rombach, Puck and Sieger, Nicholas}, title = {{Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32}, URN = {urn:nbn:de:0030-drops-200724}, doi = {10.4230/LIPIcs.SWAT.2024.32}, annote = {Keywords: Graph Isomorphism, Weisfeiler-Leman, Rank-Width, Canonization, Descriptive Complexity, Circuit Complexity} }</textarea> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> <button type="button" class="btn btn-primary copy-to-clipboard" data-selector="bibtex-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></button> </div> </div> </div> </div> </section> <section class="abstract"> <h2>Abstract</h2> <div class="content"> In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC². Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width ≤ 2k and height O(log n) (Courcelle & Kanté, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation. Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC¹. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC. </div> </section> <section class="subject-classifications mt-3"> <h2>Subject Classification</h2> <div class="acm-subject-classifications"> <h5>ACM Subject Classification</h5> <div class="content"> <ul> <li>Theory of computation → Finite Model Theory</li> <li>Theory of computation → Circuit complexity</li> <li>Theory of computation → Graph algorithms analysis</li> <li>Mathematics of computing → Graph algorithms</li> </ul> </div> </div> <div class="keywords"> <h5>Keywords</h5> <div class="content"> <ul class="list-style-comma"> <li>Graph Isomorphism</li> <li>Weisfeiler-Leman</li> <li>Rank-Width</li> <li>Canonization</li> <li>Descriptive Complexity</li> <li>Circuit Complexity</li> </ul> </div> </div> </section> <section class="metrics mt-3"> <h2>Metrics</h2> <div class="content"> <ul> <li> <a href="#" class="btn-statistics" data-entity="document/10.4230/LIPIcs.SWAT.2024.32" data-title="Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman"> <i class="bi bi-graph-up"></i> Access Statistics </a> </li> <li> Total Accesses (updated on a weekly basis) <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div>  </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context=""> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="related-version mt-3"> <h2>Related Versions</h2> <div class="content"> <ul> <li> <b>Full Version</b> <a href="https://arxiv.org/abs/2306.17777">https://arxiv.org/abs/2306.17777</a> </li> </ul> </div> </section> <section class="references mt-3"> <h2>References</h2> <div class="content"> <ol> <li> <span> V. Arvind and Piyush P. Kurur. Graph isomorphism is in SPP. Information and Computation, 204(5):835-852, 2006. URL: <a href="https://doi.org/10.1016/j.ic.2006.02.002">https://doi.org/10.1016/j.ic.2006.02.002</a>. </span> </li> <li> <span> L. Babai, E. Luks, and A. Seress. Permutation groups in NC. In STOC 1987, STOC '87, pages 409-420, New York, NY, USA, 1987. Association for Computing Machinery. URL: <a href="https://doi.org/10.1145/28395.28439">https://doi.org/10.1145/28395.28439</a>. </span> </li> <li> <span> László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In STOC'16 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684-697. ACM, New York, 2016. Preprint of full version at https://arxiv.org/abs/1512.03547v2. URL: <a href="https://doi.org/10.1145/2897518.2897542">https://doi.org/10.1145/2897518.2897542</a>. </span> </li> <li> <span> László Babai. Canonical form for graphs in quasipolynomial time: Preliminary report. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1237-1246, New York, NY, USA, 2019. Association for Computing Machinery. URL: <a href="https://doi.org/10.1145/3313276.3316356">https://doi.org/10.1145/3313276.3316356</a>. </span> </li> <li> <span> Hans L. Bodlaender. NC-algorithms for graphs with small treewidth. In J. van Leeuwen, editor, Graph-Theoretic Concepts in Computer Science, pages 1-10, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg. URL: <a href="https://doi.org/10.1007/3-540-50728-0_32">https://doi.org/10.1007/3-540-50728-0_32</a>. </span> </li> <li> <span> Harry Buhrman and Steven Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In R. K. Shyamasundar, editor, Foundations of Software Technology and Theoretical Computer Science, 12th Conference, New Delhi, India, December 18-20, 1992, Proceedings, volume 652 of Lecture Notes in Computer Science, pages 116-127. Springer, 1992. URL: <a href="https://doi.org/10.1007/3-540-56287-7_99">https://doi.org/10.1007/3-540-56287-7_99</a>. </span> </li> <li> <span> Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. Originally appeared in SFCS '89. URL: <a href="https://doi.org/10.1007/BF01305232">https://doi.org/10.1007/BF01305232</a>. </span> </li> <li> <span> Bruno Courcelle and Mamadou Kanté. Graph operations characterizing rank-width and balanced graph expressions. In Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, pages 66-75, June 2007. URL: <a href="https://doi.org/10.1007/978-3-540-74839-7_7">https://doi.org/10.1007/978-3-540-74839-7_7</a>. </span> </li> <li> <span> Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77-114, 2000. URL: <a href="https://doi.org/10.1016/S0166-218X(99)00184-5">https://doi.org/10.1016/S0166-218X(99)00184-5</a>. </span> </li> <li> <span> Bireswar Das, Anirban Dasgupta, Murali Krishna Enduri, and I. Vinod Reddy. On nc algorithms for problems on bounded rank-width graphs. Information Processing Letters, 139:64-67, 2018. URL: <a href="https://doi.org/10.1016/j.ipl.2018.07.007">https://doi.org/10.1016/j.ipl.2018.07.007</a>. </span> </li> <li> <span> Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. Information and Computation, 217:71-83, 2012. URL: <a href="https://doi.org/10.1016/j.ic.2012.05.003">https://doi.org/10.1016/j.ic.2012.05.003</a>. </span> </li> <li> <span> Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 203-214, 2009. URL: <a href="https://doi.org/10.1109/CCC.2009.16">https://doi.org/10.1109/CCC.2009.16</a>. </span> </li> <li> <span> Heinz-Dieter Ebbinghaus, J. Flum, and W. Thomas. Mathematical Logic. Springer, 2 edition, 1994. URL: <a href="https://doi.org/10.1007/978-1-4757-2355-7">https://doi.org/10.1007/978-1-4757-2355-7</a>. </span> </li> <li> <span> Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 383-392, New York, NY, USA, 2014. Association for Computing Machinery. URL: <a href="https://doi.org/10.1145/2591796.2591865">https://doi.org/10.1145/2591796.2591865</a>. </span> </li> <li> <span> Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. ACM Trans. Comput. Theory, 9(3), October 2017. URL: <a href="https://doi.org/10.1145/3132720">https://doi.org/10.1145/3132720</a>. </span> </li> <li> <span> Vyacheslav Futorny, Joshua A. Grochow, and Vladimir V. Sergeichuk. Wildness for tensors. Lin. Alg. Appl., 566:212-244, 2019. Preprint arXiv:1810.09219 [math.RT]. URL: <a href="https://doi.org/10.1016/j.laa.2018.12.022">https://doi.org/10.1016/j.laa.2018.12.022</a>. </span> </li> <li> <span> Joshua A. Grochow and Youming Qiao. Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions. arXiv:1907.00309 [cs.CC], 2019. URL: <a href="https://doi.org/10.48550/arXiv.1907.00309">https://doi.org/10.48550/arXiv.1907.00309</a>. </span> </li> <li> <span> Martin Grohe. Isomorphism testing for embeddable graphs through definability. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, pages 63-72, New York, NY, USA, 2000. Association for Computing Machinery. URL: <a href="https://doi.org/10.1145/335305.335313">https://doi.org/10.1145/335305.335313</a>. </span> </li> <li> <span> Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM, 59(5), November 2012. URL: <a href="https://doi.org/10.1145/2371656.2371662">https://doi.org/10.1145/2371656.2371662</a>. </span> </li> <li> <span> Martin Grohe and Sandra Kiefer. A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 117:1-117:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: <a href="https://doi.org/10.4230/LIPIcs.ICALP.2019.117">https://doi.org/10.4230/LIPIcs.ICALP.2019.117</a>. </span> </li> <li> <span> Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 134:1-134:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: <a href="https://doi.org/10.4230/LIPIcs.ICALP.2021.134">https://doi.org/10.4230/LIPIcs.ICALP.2021.134</a>. </span> </li> <li> <span> Martin Grohe and Daniel Neuen. Canonisation and definability for graphs of bounded rank width. ACM Trans. Comput. Log., 24(1):6:1-6:31, 2023. URL: <a href="https://doi.org/10.1145/3568025">https://doi.org/10.1145/3568025</a>. </span> </li> <li> <span> Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An improved isomorphism test for bounded-tree-width graphs. ACM Trans. Algorithms, 16(3), June 2020. URL: <a href="https://doi.org/10.1145/3382082">https://doi.org/10.1145/3382082</a>. </span> </li> <li> <span> Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded rank width. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1010-1029, 2015. URL: <a href="https://doi.org/10.1109/FOCS.2015.66">https://doi.org/10.1109/FOCS.2015.66</a>. </span> </li> <li> <span> Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 3-14. Springer, 2006. URL: <a href="https://doi.org/10.1007/11786986_2">https://doi.org/10.1007/11786986_2</a>. </span> </li> <li> <span> Lauri Hella. Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic, 43(3):235-271, 1989. URL: <a href="https://doi.org/10.1016/0168-0072(89)90070-5">https://doi.org/10.1016/0168-0072(89)90070-5</a>. </span> </li> <li> <span> Lauri Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 1996. URL: <a href="https://doi.org/10.1006/inco.1996.0070">https://doi.org/10.1006/inco.1996.0070</a>. </span> </li> <li> <span> Sang il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. URL: <a href="https://doi.org/10.1016/j.jctb.2005.10.006">https://doi.org/10.1016/j.jctb.2005.10.006</a>. </span> </li> <li> <span> Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81. Springer New York, New York, NY, 1990. URL: <a href="https://doi.org/10.1007/978-1-4612-4478-3_5">https://doi.org/10.1007/978-1-4612-4478-3_5</a>. </span> </li> <li> <span> Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: <a href="https://doi.org/10.1006/jcss.2001.1774">https://doi.org/10.1006/jcss.2001.1774</a>. </span> </li> <li> <span> Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The Weisfeiler-Leman dimension of planar graphs is at most 3. J. ACM, 66(6), November 2019. URL: <a href="https://doi.org/10.1145/3333003">https://doi.org/10.1145/3333003</a>. </span> </li> <li> <span> Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky. Interval graphs: Canonical representations in logspace. SIAM Journal on Computing, 40(5):1292-1315, 2011. URL: <a href="https://doi.org/10.1137/10080395X">https://doi.org/10.1137/10080395X</a>. </span> </li> <li> <span> Johannes Köbler, Uwe Schöning, and Jacobo Torán. Graph isomorphism is low for PP. Comput. Complex., 2:301-330, 1992. URL: <a href="https://doi.org/10.1007/BF01200427">https://doi.org/10.1007/BF01200427</a>. </span> </li> <li> <span> Johannes Köbler and Oleg Verbitsky. From invariants to canonization in parallel. In Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, and Anatol Slissenko, editors, Computer Science - Theory and Applications, pages 216-227, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. URL: <a href="https://doi.org/10.1007/978-3-540-79709-8_23">https://doi.org/10.1007/978-3-540-79709-8_23</a>. </span> </li> <li> <span> Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. On the isomorphism problem for helly circular-arc graphs. Information and Computation, 247:266-277, 2016. URL: <a href="https://doi.org/10.1016/j.ic.2016.01.006">https://doi.org/10.1016/j.ic.2016.01.006</a>. </span> </li> <li> <span> Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, January 1975. URL: <a href="https://doi.org/10.1145/321864.321877">https://doi.org/10.1145/321864.321877</a>. </span> </li> <li> <span> Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. URL: <a href="https://doi.org/10.1007/978-3-662-07003-1_1">https://doi.org/10.1007/978-3-662-07003-1_1</a>. </span> </li> <li> <span> Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. SIAM Journal on Computing, 46(1):161-189, 2017. URL: <a href="https://doi.org/10.1137/140999980">https://doi.org/10.1137/140999980</a>. </span> </li> <li> <span> Rudolf Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131-136, 1979. URL: <a href="https://doi.org/10.1016/0020-0190(79)90004-8">https://doi.org/10.1016/0020-0190(79)90004-8</a>. </span> </li> <li> <span> Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualization-refinement algorithms for graph isomorphism. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 138-150. ACM, 2018. URL: <a href="https://doi.org/10.1145/3188745.3188900">https://doi.org/10.1145/3188745.3188900</a>. </span> </li> <li> <span> Sang-il Oum. Rank-width is less than or equal to branch-width. Journal of Graph Theory, 57(3):239-244, 2008. URL: <a href="https://doi.org/10.1002/jgt.20280">https://doi.org/10.1002/jgt.20280</a>. </span> </li> <li> <span> Uwe Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312-323, 1988. URL: <a href="https://doi.org/10.1016/0022-0000(88)90010-4">https://doi.org/10.1016/0022-0000(88)90010-4</a>. </span> </li> <li> <span> Thomas Thierauf and Fabian Wagner. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory Comput. Syst., 47(3):655-673, 2010. URL: <a href="https://doi.org/10.1007/S00224-009-9188-4">https://doi.org/10.1007/S00224-009-9188-4</a>. </span> </li> <li> <span> Jacobo Torán. On the hardness of graph isomorphism. SIAM J. Comput., 33(5):1093-1108, 2004. URL: <a href="https://doi.org/10.1137/S009753970241096X">https://doi.org/10.1137/S009753970241096X</a>. </span> </li> <li> <span> Oleg Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. In STACS 2007, pages 682-693, Berlin, Heidelberg, 2007. Springer-Verlag. URL: <a href="https://doi.org/10.5555/1763424.1763505">https://doi.org/10.5555/1763424.1763505</a>. </span> </li> <li> <span> Fabian Wagner. Graphs of bounded treewidth can be canonized in AC¹. In Proceedings of the 6th International Conference on Computer Science: Theory and Applications, CSR'11, pages 209-222, Berlin, Heidelberg, 2011. Springer-Verlag. URL: <a href="https://doi.org/10.1007/978-3-642-20712-9_16">https://doi.org/10.1007/978-3-642-20712-9_16</a>. </span> </li> </ol> </div> </section> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60" /> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60" /> <br/> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2024-10-22"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/document/10.4230/LIPIcs.SWAT.2024.32/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { const innerAnchors = [ 'resource-articles', 'cfp-si-resources', 'cfp-si-autonomous-systems-and-knowledge-graphs' ]; let anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } $('[data-tab-link]').on('click', function(e) { const $target = $(e.currentTarget); let href = $target.attr('href'); let scrollLink = null; if (href === '#cfp-si-list') { scrollLink = href; href = '#cfp'; } try { console.log(href); $(href+'-tab').tab('show'); } catch(e) { } console.log(scrollLink); if (scrollLink !== null) { setTimeout(function() { $(scrollLink)[0].scrollIntoView(); }, 200); } else { setTimeout(function() { window.scrollTo(0,0); }, 200); } }); } }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>

CINXE.COM

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman