Symmetry Breaking in Graceful Graphs

Abstract

Symmetry in a Constraint Satisfaction Problem can cause wasted search, which can be avoided by adding constraints to the CSP to exclude symmetric assignments or by modifying the search algorithm so that search never visits assignments symmetric to those already considered. Two such approaches are SBDS (Symmetry Breaking During Search) and SBDD (Symmetry Breaking by Dominance Detection); modifications of these are GAP-SBDS and GAP-SBDD, which work with the symmetry group rather than the individual symmetries. There has been little experience of how these techniques compare in practice. We compare SBDS, GAP-SBDS and GAP-SBDD in finding all graceful labellings of graphs with symmetry. For these problems, the benefits of GAP-SBDS over SBDS outweigh the additional overheads, except when the number of symmetries is small. When simple constraints can be found to break all the symmetry, they can give beter problem-solving performance than GAP-SBDS; however, if the constraints break only part of the symmetry, GAP-SBDS does less search and is faster. Surprisingly, GAP-SBDD is slower than GAP-SBDS for these problems, and we show that this is due to a feature of the CSP model. Eliminating symmetry has allowed us to find all graceful labellings, or prove that there are none, for several graphs whose gracefulness was not previously known.

Back to "Barbara Smith - Publications on Constraint Programming"