Breaking Symmetries with Involutions
This work addresses a fundamental challenge in combinatorial search and graph theory, offering improved symmetry-breaking methods that could enhance efficiency in applications like constraint satisfaction and graph isomorphism testing.
The paper tackles the problem of symmetry breaking for graphs, which is computationally hard, by introducing constraints based on graph patterns derived from involutions, resulting in small-sized constraints that break many symmetries.
Symmetry breaking for graphs and other combinatorial objects is notoriously hard. On the one hand, complete symmetry breaks are exponential in size. On the other hand, current, state-of-the-art, partial symmetry breaks are often considered too weak to be of practical use. Recently, the concept of graph patterns has been introduced and provides a concise representation for (large) sets of non-canonical graphs, i.e.\ graphs that are not lex-leaders and can be excluded from search. In particular, four (specific) graph patterns apply to identify about 3/4 of the set of all non-canonical graphs. Taking this approach further we discover that graph patterns that derive from permutations that are involutions play an important role in the construction of symmetry breaks for graphs. We take advantage of this to guide the construction of partial and complete symmetry breaking constraints based on graph patterns. The resulting constraints are small in size and strong in the number of symmetries they break.