LIPIcs.ESA.2021.6.pdf
- Filesize: 0.71 MB
- 18 pages
Document
Parallel Computation of Combinatorial Symmetries
Authors
-
Part of:
Volume:
29th Annual European Symposium on Algorithms (ESA 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-31
File
Document Identifiers
Acknowledgements
We thank Adolfo Piperno, Brendan McKay, Tommi Junttila, and Petteri Kaski for discussions providing us with deeper insights into their isomorphism solvers. We also want to thank our colleagues Thomas Schneider, Jendrik Brachter, and Moritz Lichter for the fruitful discussions we had on some of the topics in this paper.
Cite AsGet BibTex
Markus Anders and Pascal Schweitzer. Parallel Computation of Combinatorial Symmetries. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.6
https://doi.org/10.4230/LIPIcs.ESA.2021.6
Abstract
In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task.
We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization.
We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
- Theory of computation → Shared memory algorithms
Keywords
- graph isomorphism
- automorphism groups
- algorithm engineering
- parallel algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- dejavu. URL: http://alg.cs.uni-kl.de/en/team/anders/dejavu/.
- nauty and Traces. URL: http://pallini.di.uniroma1.it.
- Markus Anders and Pascal Schweitzer. Engineering a fast probabilistic isomorphism test. In 2021 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). SIAM, 2021. to appear. URL: https://doi.org/10.1137/1.9781611976472.6.
- Vijaya Balpande and Anjali Mahajan. Article: Parallelization of graph isomorphism using OpenMP. International Journal of Computer Applications, 117(8):33-41, May 2015. Full text available. URL: https://doi.org/10.5120/20576-2982.
- Duc-Hiep Chu and Joxan Jaffar. A complete method for symmetry reduction in safety verification. In Proceedings of the 24th international conference on Computer Aided Verification, volume 7358 of Lecture Notes in Computer Science, pages 616-633. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31424-7_43.
- Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah, Igor L. Markov, and Igor L. Markov. Exploiting structure in symmetry detection for CNF. In Proceedings of the 41st Annual Design Automation Conference, DAC '04, pages 530-534, New York, NY, USA, 2004. ACM. URL: https://doi.org/10.1145/996566.996712.
- Robert Gens and Pedro M. Domingos. Deep symmetry networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems, pages 2537-2545, 2014. URL: https://dl.acm.org/doi/abs/10.5555/2969033.2969110.
- Ian P. Gent, Karen E. Petrie, and Jean-François Puget. Symmetry in constraint programming. In Francesca Rossi, Peter van Beek, and Toby Walsh, editors, Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence, pages 329-376. Elsevier, 2006. URL: https://doi.org/10.1016/S1574-6526(06)80014-3.
- Patrice Godefroid. Exploiting symmetry when model-checking software. In Proceedings of the IFIP TC6 WG6.1 Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols (FORTE XII) and Protocol Specification, Testing and Verification (PSTV XIX), volume 156 of IFIP Conference Proceedings, pages 257-275. Kluwer, 1999. URL: https://doi.org/10.1007/978-0-387-35578-8_15.
- Marijn J. H. Heule and Oliver Kullmann. The science of brute force. Communications of the ACM, 60(8):70-79, 2017. URL: https://doi.org/10.1145/3107239.
- Tommi A. Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.13.
- Hadi Katebi, Karem A. Sakallah, and Igor L. Markov. Symmetry and satisfiability: An update. In Ofer Strichman and Stefan Szeider, editors, Theory and Applications of Satisfiability Testing - SAT 2010, 13th International Conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings, volume 6175 of Lecture Notes in Computer Science, pages 113-127. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-14186-7_11.
- Martin Kutz and Pascal Schweitzer. Screwbox: a randomized certifying graph-non-isomorphism algorithm. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.14.
- Leo Liberti. Symmetry in mathematical programming. In Jon Lee and Sven Leyffer, editors, Mixed Integer Nonlinear Programming, pages 263-283, New York, NY, 2012. Springer New York. URL: https://doi.org/10.1007/978-1-4614-1927-3_9.
- Yanxi Liu, Hagit Hel-Or, Craig S. Kaplan, and Luc Van Gool. Computational symmetry in computer vision and computer graphics. Foundations and Trends in Computer Graphics and Vision, 5(1-2):1-195, 2010. URL: https://doi.org/10.1561/9781601983657.
- José Luis López-Presa, Luis Núñez Chiroque, and Antonio Fernández Anta. Novel techniques for automorphism group computation. In Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings, volume 7933 of LNCS, pages 296-307. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38527-8_27.
- Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60(0):94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
- Alice Miller, Alastair F. Donaldson, and Muffy Calder. Symmetry in temporal logic model checking. ACM Computing Surveys, 38(3), 2006. URL: https://doi.org/10.1145/1132960.1132962.
- 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.
- Irene Luque Ruiz and Miguel Ángel Gómez-Nieto. A Java tool for the management of chemical databases and similarity analysis based on molecular graphs isomorphism. In Computational Science - ICCS 2008, 8th International Conference, Kraków, Poland, June 23-25, 2008, Proceedings, Part II, volume 5102 of LNCS, pages 369-378. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-69387-1_41.
- Ákos Seress. Permutation Group Algorithms. Cambridge Tracts in Mathematics. Cambridge University Press, 2003. URL: https://doi.org/10.1017/CBO9780511546549.
- Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539-2561, 2011. URL: https://doi.org/10.5555/1953048.2078187.
-
Greg Daniel Tener. Attacks on Difficult Instances of Graph Isomorphism: Sequential and Parallel Algorithms. PhD thesis, University of Central Florida, Orlando, FL, USA, 2009. AAI3401107.
