  There are numerous NP-hard combinatorial problems which involve searching for
an undirected graph satisfying a certain property. One way to solve such
problems is to translate a problem into an instance of the boolean
satisfiability (SAT) or constraint satisfaction (CSP) problem. Such reduction
usually can give rise to numerous isomorphic representations of the same graph.
One way to reduce the search space and speed up the search under these
conditions is to introduce symmetrybreaking predicates. In this paper we
introduce three novel and practically effective symmetry-breaking predicates
for an undirected connected graph search based on breadth-first search (BFS)
enumeration and compare with existing symmetry-breaking methods on several
graph problems.

Data Structures and Algorithms