Summary
Source Code
References
People
Other Tools
Acknowledgments
Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. However, existing tools suffer quadratic runtime in the number of symmetries explicitly returned and are of limited use on very large, sparse, symmetric graphs. This paper introduces a new symmetry-discovery algorithm which exploits the sparsity present not only in the input but also the output, i.e., the symmetries themselves. By avoiding quadratic runtime on large graphs, it improves state-of-the-art runtimes from several days to less than a second.
The latest version of saucy is available upon request. Send an email to saucy.request@gmail.com, and tell us your name, affiliation, intended use of saucy and whether you agree to the terms of the saucy license.
Graph Automorphism from Wolfram Mathworld
P. T. Darga, K. A. Sakallah, and I. L. Markov, “Faster Symmetry Discovery using Sparsity of Symmetries”, Proceedings of the 45st Design Automation Conference, Anaheim, California, June 2008. [pdf] [ppt] [empirical results].
R. C. Johnson, “ Saucy algorithm exploits symmetries,&rdquo EE Times, June 2008.
P. T. Darga, M. H. Liffiton, K. A. Sakallah, and I. L. Markov, “Exploiting Structure in Symmetry Generation for CNF”, Proceedings of the 41st Design Automation Conference, pp. 530-534, San Diego, California, June 2004. [pdf] [ppt]
Paul T. Darga
Mark Liffiton
Karem Sakallah
Igor Markov
All research was performed at the University of Michigan, in the Electrical Engineering and Computer Science department.
nauty: the original graph symmetry and canonical labeling program, by Brendan McKay.
bliss: another symmetry and canonical labeling program, by Tommi Junttila and Patteri Kaski.
shatter: adds symmetry-breaking predicates to CNF formulas to assist in determining their satisfiability, by Fadi Aloul.
This work was funded in part by the National Science Foundation and by the DARPA/MARCO Gigascale Systems Research Center.