
Breaking Symmetries in Graph Search with Canonizing SetsAvraham Itzhakov and Michael Codish
Constraints;
21 (3): 357374,
2016
Abstract:There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only nonisomorphic solutions. For small search problems, with up to $10$ vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fullyinterchangeable matrix search problems.Available: bibtex entry Related sites: from the arXiv from springer Michael Codish The Department of Computer Science BenGurion University of the Negev PoB 653, BeerSheva, 84105, Israel mcodish@cs.bgu.ac.il
