TY - JOUR

T1 - Symmetry definitions for constraint satisfaction problems

AU - Cohen, D

AU - Jeavons, P

AU - Jefferson, Christopher Anthony

AU - Petrie, Karen Elizabeth

AU - Smith, B M

PY - 2006/7

Y1 - 2006/7

N2 - We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.

AB - We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.

KW - constraint satisfaction problems

KW - symmetry

KW - EXPLOITING SYMMETRIES

KW - SEARCH

UR - http://www.scopus.com/inward/record.url?scp=33745225485&partnerID=8YFLogxK

U2 - 10.1007/s10601-006-8059-8

DO - 10.1007/s10601-006-8059-8

M3 - Article

SN - 1572-9354

VL - 11

SP - 115

EP - 137

JO - Constraints

JF - Constraints

ER -