2026-07-21T23:53:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23869 2025-11-12T13:10:42Z ddc:004 open_access

Breaking Symmetries with Involutions Codish, Michael Janota, Mikoláš graph symmetry patterns permutation Ramsey graphs greedy CEGAR 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Codish and Mikoláš Janota 2025 Is Part Of LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2025.8 urn:nbn:de:0030-drops-238699 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode