# An adaptive prefix-assignment technique for symmetry reduction

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2017.

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

- [The Complexity of Symmetry Breaking Beyond Lex-Leader](https://mlsanity.com/paper/2407.04419/) (2024)
- [Orbitopal Fixing in SAT](https://mlsanity.com/paper/2601.16855/) (2026)

## Abstract (arXiv)

This paper presents a technique for symmetry reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework [J.~Algorithms 26 (1998), no.~2, 306--324]. Among key features of the technique are (i) adaptability---the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries; (ii) parallelizability---prefix-assignments can be processed in parallel independently of each other; (iii) versatility---the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph; and (iv) implementability---the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface.