License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.1
URN: urn:nbn:de:0030-drops-183511
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18351/
Anders, Markus ;
Schweitzer, Pascal ;
Stieß, Julian
Engineering a Preprocessor for Symmetry Detection
Abstract
State-of-the-art solvers for symmetry detection in combinatorial objects are becoming increasingly sophisticated software libraries. Most of the solvers were initially designed with inputs from combinatorics in mind (nauty, bliss, Traces, dejavu). They excel at dealing with a complicated core of the input. Others focus on practical instances that exhibit sparsity. They excel at dealing with comparatively easy but extremely large substructures of the input (saucy). In practice, these differences manifest in significantly diverging performances on different types of graph classes.
We engineer a preprocessor for symmetry detection. The result is a tool designed to shrink sparse, large substructures of the input graph. On most of the practical instances, the preprocessor improves the overall running time significantly for many of the state-of-the-art solvers. At the same time, our benchmarks show that the additional overhead is negligible.
Overall we obtain single algorithms with competitive performance across all benchmark graphs. As such, the preprocessor bridges the disparity between solvers that focus on combinatorial graphs and large practical graphs. In fact, on most of the practical instances the combined setup significantly outperforms previous state-of-the-art.
BibTeX - Entry
@InProceedings{anders_et_al:LIPIcs.SEA.2023.1,
author = {Anders, Markus and Schweitzer, Pascal and Stie{\ss}, Julian},
title = {{Engineering a Preprocessor for Symmetry Detection}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {1:1--1:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18351},
URN = {urn:nbn:de:0030-drops-183511},
doi = {10.4230/LIPIcs.SEA.2023.1},
annote = {Keywords: graph isomorphism, automorphism groups, symmetry detection, preprocessors}
}
