Symmetry in Finite Combinatorial Objects: Scalable Methods and Applications

Symmetries of combinatorial objects are known to complicate search algorithms, but such obstacles can often be removed by detecting symmetries early and discarding symmetric subproblems. Canonical labeling of combinatorial objects facilitates easy equivalence checking through quick matching. All existing canonical-labeling software also finds symmetries, but the fastest symmetry-finding software does not perform canonical labeling. In this thesis, we describe highly scalable symmetry-detection algorithms for two combinatorial objects: graphs and Boolean functions. Our algorithms are based on a decision tree that combines elements of group-theoretic computation with branching and backtracking search. Moreover, we contrast the search for graph symmetries and a canonical labeling to dissect typical algorithms and identify their similarities and differences. We develop a novel approach to graph canonical labeling where symmetries are found first and then used to speed up the canonical-labeling routines. Empirical results show that our symmetry-detection and canonical-labeling algorithms outperform the state of the art.