Symmetry Definitions

The issue of symmetry is now widely recognised as of fundamental importance in constraint satisfaction problems (CSPs). It seems self-evident that in order to deal with symmetry we should first agree what we mean by symmetry. Surprisingly, this appears not to be true: researchers in this area have defined symmetry in fundamentally different ways, whilst often still identifying the same collection of symmetries in a given problem and dealing with them in the same way. In this paper, we first survey the various symmetry definitions that have appeared in the literature. We show that the existing definitions reflect two distinct views of symmetry: that symmetry is a property of the solutions, i.e., that any mapping that preserves the solutions is a symmetry; or that symmetry preserves the constraints, and therefore as a consequence also preserves the solutions. We propose two new definitions of solution symmetry and constraint symmetry to capture these two distinct views, and show that they are indeed different: although any constraint symmetry is also a solution symmetry, there can be many solution symmetries that are not constraint symmetries. We discuss the relationship between the symmetry groups identified by these definitions and show that each is the automorphism group of a hypergraph, derived from either the solutions or the constraints of the CSP.


Symmetry Definitions for Constraint Satisfaction Problems
David Cohen & Peter Jeavons & Christopher Jefferson &
Karen E. Petrie & Barbara M. Smith

http://web.comlab.ox.ac.uk/people/Peter.Jeavons/