Graph search problems are fundamental in graph theory. Such problems include: existence problems, where the goal is to determine whether a simple graph with certain graph properties exists, enumeration problems, which are about finding all solutions modulo graph isomorphism, and extremal problems, where we seek the smallest/largest solution with respect to some target such as the number of edges or vertices in a solution. Solving graph search problems is typically hard due to the enormous search space and the large number of symmetries. One common approach to break symmetries in constraint programming is to add symmetry breaking constraints which are satisfied by at least one member of each isomorphism class. A symmetry breaking constraint is called complete if it is satisfied by exactly one member of each isomorphism class and partial otherwise. A universal measure for the size of a symmetry breaking constraint is the size of its representation in propositional logic. All known techniques to define complete symmetry breaking constraints for graph search problems are based on predicates which are exponential in size. There is no known polynomial size complete symmetry breaking constraint for graph search problems. This paper introduces, for the first time, a complete symmetry breaking constraint of polynomial size for a significant class of graphs: the class of uniquely Hamiltonian graphs. This is the class of graphs that contain exactly one Hamiltonian cycle. We introduce a canonical form for uniquely Hamiltonian graphs and prove that testing whether a given uniquely Hamiltonian graph is canonical can be performed efficiently. Based on this canonicity test, we construct a complete symmetry breaking constraint of polynomial size which is satisfied only by uniquely Hamiltonian graphs which are canonical. We apply the proposed symmetry breaking constraint to determine the, previously unknown, smallest orders for which uniquely Hamiltonian graphs of minimum degree 3 and girths 3 and 4 exist. Given that it is unknown if there exist polynomial sized complete symmetry breaking constraints for graphs, this paper makes a first step in the direction of identifying specific classes of graphs for which such constraints do exist.
展开▼
