# The Complexity of Symmetry Breaking Beyond Lex-Leader

arXiv: https://arxiv.org/abs/2407.04419 · HTML: https://mlsanity.com/paper/2407.04419/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 42 references that are in the map.
- First posted on arXiv 5 Jul 2024.

## Builds on (most cited first, 4 of 4)

- [Certified Symmetry and Dominance Breaking for Combinatorial Optimisation](https://mlsanity.com/paper/2203.12275/) (2022)
- [A Commentary on "Breaking Row and Column Symmetries in Matrix Models"](https://mlsanity.com/paper/1910.01423/) (2019)
- [An adaptive prefix-assignment technique for symmetry reduction](https://mlsanity.com/paper/1706.08325/) (2017)
- [On the Complexity of Breaking Symmetry](https://mlsanity.com/paper/2005.08954/) (2020)

## Built on by (most cited first, 1 of 1)

- [Breaking the Symmetries of Indistinguishable Objects](https://mlsanity.com/paper/2503.17251/) (2025)

## Abstract (arXiv)

Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs.