Lightweight Detection of Variable Symmetries for Constraint Satisfaction
Christophe Lecoutre, Sébastien Tabary · 2009
In this paper, we propose to automatically detect variable symmetries of CSP instances by computing for each constraint scope a partition exhibiting locally symmetric variables. From this local information obtained in polynomial time, we can build a so-called LSV-graph whose automorphisms correspond to (global) variable symmetries. Interestingly enough, our approach allows us to disregard the representation (extension, intension, global) of constraints. Besides, the size of the LSV-graph is linear with respect to the number of constraints (and their arity).