We investigate rules which allow variable elimination in binary CSP (constraint satisfaction problem) instances while conserving satisfiability. We propose new rules and compare them, both theoretically and experimentally. We give optimised algorithms to apply these rules and show that each defines a novel tractable class. Using our variable-elimination rules in preprocessing allowed us to solve more benchmark problems than without.

The study of broken-triangles is becoming increasingly ambitious, by both solving constraint satisfaction problems (CSPs) in polynomial time and reducing search space size through value merging or variable elimination. Considerable progress has been made in extending this important concept, such as dual broken-triangle and weakly broken-triangle, in order to maximize the number of captured tractable CSP instances and/or the number of merged values. Specifically, m-wBTP allows to merge more values than BTP. k-BTP, WBTP and m-BTP permit to capture more tractable instances than BTP. Here, we introduce a new weaker form of BTP, which will be called m-fBTP for flexible broken-triangle property. m-fBTP allows on the one hand to eliminate more variables than BTP while preserving satisfiability and on the other to define new bigger tractable class for which arc consistency is a decision procedure. Likewise, m-fBTP permits to merge more values than BTP but less than m-wBTP.

Identifying tractable classes of constraint satisfaction problems (CSPs) has been studied over the past two decades, and is now a very active research domain. Recently, some works have shown the interest of these tractable classes from a different viewpoint. For example, it is known that if there is no broken triangle on each two values of a given variable in an arc-consistent binary CSP, then this variable can be eliminated without changing its satisfiability. Next, it has been proved that even when this rule cannot be applied, it may be the case that for a given pair of values no broken triangle occurs, if this is the case, then we can perform a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper, we show that partial or total presence of tractable properties in non-binary constraints is sufficient for them to be decomposable into a set of lower arity constraints while preserving equivalence. More precisely, we prove that the presence of bijection or Dual Broken Triangle Property in non-binary constraint permits to decompose it while preserving equivalence.

Considerable research effort has been focused on the translation of non-binary CSP into an equivalent binary CSP. Most of this work has been devoted to studying the binary encoding of non-binary CSP. Three encodings have been proposed, namely dual encoding, hidden variable encoding and double encoding. Unfortunately, such encodings do not allow to use some properties and interesting results defined only for the binary case. Another approach consists in the transformation of each non-binary constraint into a set of binary constraints: the CSP obtained is called primal. Unfortunately, this transformation does not preserve satisfiability. In this paper, we propose some conditions under which a non-binary constraint can be decomposed into a set of binary constraints while preserving satisfiability. An experimental study proves that our approach is not artificial since some ternary benchmarks can be transformed into equivalent binary instances and effectively solved by MAC.

Tractable classes constitute an important issue in CP, at least from a theoretical viewpoint. But they are not actually used in practice. Either their treatment is too costly for time complexity or, even if there exist efficient algorithms to manage them, they do not appear in the real problems. We propose here to address this issue thanks to the notion of hidden tractable classes. Such classes are based on a known tractable class C, and a transformation t, and are defined by sets of instances P such that their transformation using t is in C, that is t (P) in C. We propose a general framework to study such notions. After, we focus our study on the tractable class BTP, and several transformations which are the filterings classically used in CP. We show then that the use of filterings allows sometimes to highlight the occurrence of BTP in the benchmarks generally considered for solver comparisons, i.e. That BTP is sometimes "hidden" in the benchmarks. Thus, this approach allows to extend the set of known tractable classes.

Find new islands of tractability, that is classes of CSPs for which polytime algorithms exist, is a fundamental task in the study of constraint satisfaction problems. The concept of hybrid tractable class, which allows to deal simultaneously with the restrictions of languages and, for example, the satisfaction of structural properties, is an approach which has already shown its interest in this domain. Here we study a hybrid class for non-binary CSPs. With this aim in view, we consider the tractable class BTP introduced in [1].While this class has been defined for binary CSPs, the authors have suggested to extend it to CSPs with constraints of arbitrary arities, using the dual representation of such CSPs. We develop this idea by proposing a new definition without exploiting the dual representation, but using a semantic property associated to the compatibility relations of the constraints. This class, called DBTP for Dual BTP, is firstly shown to be tractable. Then it is compared to some known classes. In particular, we prove that DBTP is incomparable with BTP and that it includes some well known classes of CSPs such as beta-acyclic CSPs.