Summary
Source Code
References
People Involved in this Research
Related Software 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
H. Katebi, K. A. Sakallah and I. L. Markov,
``Conflict Anticipation in the Search for Graph Automorphisms''
in Proc.
Int'l Conf. on Logic for Programming, Artificial Intelligence
and Reasoning (LPAR), pp. 243-257, Mérida, Venezuela, 2012.
H. Katebi, K. A. Sakallah, I. L. Markov, ``Symmetry and Satisfiability: An Update,'' in Proc. Satisfiability Symposium (SAT), Edinburgh, Scotland, July 2010.
P. T. Darga, K. A. Sakallah, and I. L. Markov,
“Faster Symmetry Discovery using Sparsity of Symmetries”,
Proceedings of
the 45th Design Automation Conference, Anaheim, California, June 2008.
[ppt]
[empirical results].
R. C. Johnson, “ Saucy algorithm exploits symmetries,'' EE Times, June 2008.
P. T. Darga, M. H. Liffiton, K. A. Sakallah, and I. L. Markov,
“Exploiting Structure in Symmetry Detection for CNF”,
Proceedings of
the 41st Design Automation Conference, pp. 530-534, San Diego,
California, June 2004.
[ppt]
Paul T. Darga
Hadi Katebi
Mark Liffiton
Igor Markov
Karem Sakallah
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.
traces: a canonical labeling package by Adolfo Piperno
nishe: a canonical labeling package by Greg Tener
conauto: a graph ismorphism package by José Luis López-Presa
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.