Arities of Symmetry Breaking Constraints

Abstract. Static symmetry breaking is a well-established technique to speed up the solving process of symmetric Constraint Satisfaction Pro-grams (csps). Static symmetry breaking suffers from two inherent prob-lems: symmetry breaking constraints come in great numbers and are of high arity. Here, we consider the problem of high arity. We prove that not even for binary csps can we always reduce the arity of the com-monly used lexleader constraints. We further prove that for binary csps we sometimes have to rely on at least ternary constraints to break all symmetries. On the positive side, we prove that symmetry breaking con-straints with arity bn/2c+1 exist that always break the symmetries of a csp completely. For various special cases of csps, we prove that binary symmetry breaking constraints may break all symmetries.