Breaking Symmetries from a Set-Covering Perspective
This work addresses symmetry breaking for computational graph analysis, offering incremental improvements with new theoretical insights.
The paper tackles the problem of symmetry breaking in graphs by formalizing it as a set-covering problem, leading to optimal LexLeader symmetry breaks for graphs up to order 10 and partial breaks that improve on state-of-the-art methods.
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\leq 10$ as well as to partial symmetry breaks which improve on the state-of-the-art.