2025/02/14 by Michael Codish, Mikoláš Janota, Codish, Michael +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #FOS: Computer and information sciences #Fractal and DNA sequence analysis #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.2502.10056
openalex publication_date 2025/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We formalize symmetry breaking as a set-covering problem. For the case of breaking symmetries on graphs, a permutation covers a graph if applying it to the graph yields a smaller graph in a given order. Canonical graphs are those that cannot be made smaller by any permutation. A complete symmetry break is then a set of permutations that covers all non-canonical graphs. A complete symmetry break with a minimal number of permutations can be obtained by solving an optimal set-covering problem. The challenge is in the sizes of the corresponding set-covering problems and in how these can be tamed. The set-covering perspective on symmetry breaking opens up a range of new opportunities deriving from decades of studies on both precise and approximate techniques for this problem. Application of our approach leads to optimal LexLeader symmetry breaks for graphs of order n≤ 10 as well as to partial symmetry breaks which improve on the state-of-the-art.