Unifying and extending hybrid tractable classes of CSPs

Abstract

Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-complete task. Many works have been concerned with identifying tractable classes of CSPs. Tractability is obtained by imposing specific problem structures, specific constraint relations or both. A tractable CSP class whose tractability is due to both structural and relational properties is said to be hybrid. In this article, we present a hybrid tractable CSP class that brings together and generalises many known hybrid tractable CSPs. The proposed class is characterised by means of simple but powerful notions from set theory.

• constraint satisfaction
• tractable CSP
• ranked CSP
• set theory

Notes

1. The form of the following tuple will slightly differ in the case where j is equal to 1, r − 1 or r.

2. The number is known as the width of the ordered hypergraph (Dechter 2003) and we have in sparse hypergraphs. Another point worth-mentioning is that .

3. See Lemma 3 of Cooper et al. (2010).

4. The following statements correspond to the configuration depicted in Figure 1(c).