

![0_image_0.png](0_image_0.png)

## 6 Work In Progress

In this paper we surveyed several forms of interchangeability, presented their definitions, and analyzed their relationship. This document is a work in progress.

In the expanded version, we will address in depth the following topics:
More about interchangeability: concepts not mentioned here; missing proofs of incomparability; the satisfiability-preserving property; restrictions to constraint types; algorithms for interchangeability and their complexity; experimental results.

Beyond classical CSPs: soft constraints [Cooper, 2003; Bistarelli *et al.*, 2003; Neagu *et al.*, 2003; Neagu and Faltings, 2003]; distributed CSPs [Petcu and Faltings, 2003; Burke and Brown, 2006; Ezzahir *et al.*, 2007].

Relation to symmetry: various types [Benhamou, 1994; Cohen *et al.*, 2006];
symmetry breaking during search (SBDS) [Roney-Dougal *et al.*, 2004; Backofen and Will, 2002; Gent and Smith, 2000], symmetry breaking by dominance detection (SBDD) [Fahle *et al.*, 2001; Focacci and Milano, 2001], and symmetry breaking by enforcing variable or domain ordering [Bellicha *et al.*,
1994; Yip and Hentenryck, 2009]; restricted classes of symmetries and problems where the symmetry is broken in polynomial time [Hentenryck *et al.*,
2003; Benhamou, 2004].

Relation to search-space compaction: as in CPR [Hubbe and Freuder, 1992],
AND/OR graphs [Dechter and Mateescu, 2004], SLDD [Wilson, 2005], and solution robustness [Ginsberg *et al.*, 1998; Hebrard *et al.*, 2004].

Relation to SAT solving.