On a new extension of BTP for binary CSPs

Abstract

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 either 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 us to merge more values than BTP. DBTP, ∀∃-BTP, k-BTP, WBTP and m-wBTP permit us to capture more tractable instances than BTP. However, except BTP, none of these extensions allows variable elimination while preserving satisfiability. Moreover, k-BTP and m-wBTP define bigger tractable classes around BTP but both of them generally need a high level of consistency. Here, we introduce a new weaker form of BTP, called m-fBTP for flexible broken-triangle property, which will represent a compromise between most of these previous tractable properties based on BTP. m-fBTP allows us on the one hand to eliminate more variables than BTP while preserving satisfiability and on the other to define a new bigger tractable class for which arc consistency is a decision procedure. Likewise, m-fBTP permits to merge more values than BTP but fewer than m-wBTP. The binary CSP instances satisfying m-fBTP are solved by algorithms of the state-of-the-art like MAC and RFL in polynomial time. An open question is whether it is possible to compute, in polynomial time, the existence of some variable ordering for which a given instance satisfies m-fBTP.

1 Introduction

A wide range of real-life problems issue from Artificial Intelligence (AI) and Operational Research (OR) like spatial and temporal planning, scheduling and configuration can be expressed as a binary Constraint Satisfaction Problems (CSPs [1]). A binary CSP consists of a set of variables X, each one has a finite set of values called domain D, and a finite set of constraints C. Each constraint is defined over a pair of variables and represents a set of valid assignment of values to these two variables, involved by the constraint. A solution to a CSP instance is an assignment of value to each variable satisfying all the constraints. Checking whether a given CSP instance has a solution is known to be NP-complete.

In general, the main techniques to achieve this task are based on backtracking algorithms, whose worst-case time complexity is $O(ed^{n})$ where e, n and d are the number of constraints, the number of variables and the maximum domain size, respectively. In order to reduce this exponential time complexity, many different approaches have been proposed. The first one, called filtering by consistency, consists of removing inconsistent values [2], values which cannot take part in any solution. Obviously this approach leaves the set of solutions unchanged. The second relies on merging values (consistent or inconsistent), satisfying some conditions, without affecting the existence of a solution [3,4,5,6]. The last eliminates variables [7, 8] or constraints [9] while preserving the satisfiability of the instance.

In a somewhat orthogonal direction, much research has been devoted to identifying tractable classes. In the literature, several tractable classes have been defined but the Broken-Triangle Property (BTP [10, 11]) still remains at the heart of this research area. This property has some interesting characteristics from a solving viewpoint as well as reduction operations viewpoint. Indeed, BTP is not only defined for solving CSP in polynomial time, but also for reducing the size of CSP instances while preserving satisfiability. Specifically, the absence of broken-triangles has led, under some conditions, to variable elimination [7, 8] or domain reduction by value merging [5, 6] while preserving satisfiability.

More recently, it has been proved that the presence of certain broken-triangles does not necessarily preclude defining tractable classes [12,13,14,15,16,17,18,19] and/or merging values [19]. For example, ETP [16] and more generally k-BTP [17] authorizes some broken-triangles and defines larger tractable classes than BTP but does not permit value merging. Likewise, m-wBTP [19] does not forbid all broken-triangles and defines a maximal value-merging condition. Unfortunately, none of them allow variable elimination (see [19]) although the initial definition of BTP permits it [8]. Moreover, k-BTP seems to be unusable beyond $k = 3$ and m-wBTP appears to be inexploitable when $m>2$ because of the level of consistency required.

The main contribution of this work is providing a new weaker-form of BTP, called m-fBTP, which allows value merging, variable elimination and defines a new hybrid tractable class for which arc consistency is a decision procedure. The results proven in this paper also provide theoretical insight into the relationship between m-fBTP and some others previous extension of BTP.

So, our paper will be organized as follows: Section 2 recalls some definitions and notations. In Section 3, we introduce the flexible broken-triangle property. Next, we show that m-fBTP is a maximal variable-elimination condition. Section 5 proves that m-fBTP instances defines a tractable class which can be efficiently solved by algorithms of the state-of-the-art like MAC [20] and RFL [21]. In section 6, we compare m-fBTP to some known tractable classes like DBTP, $\forall \exists$-BTP [13], k-BTP, m-wBTP and WBTP [18]. After, we experimmentally show the existence of our patterns in benchmark problems of the CSP competition 2008. Finally we give a discussion and perspective for future work. Some results of this paper first published in [22].

2 Formal background

Constraint satisfaction problems constitute an important tool for modeling and solving many different practical problems in Artificial Intelligence and Operations Research. A non-binary CSP instance, also called n-ary, is defined as below:

Definition 1 (CSP instance)

A CSP instance is a pair $I=(X,C)$ with:

• X: a set of n variables denoted by $\{x_{1},...,x_{n}\}$. Each variable $x_{i}$ has a domain $D(x_{i})$ containing at most d values.

• C: a set of e constraints. Each constraint $C_{i}$ is a pair $(Scp(C_{i}),Rel(C_{i}))$ where:

  • $Scp(C_{i}) = \{ x_{i_{1}},...,x_{i_{a_{i}}} \} \subseteq X$, is the scope of $C_{i}$,

  • $Rel(C_{i}) \subseteq D(x_{i_{1}}) \times ... \times D(x_{i_{a_{i}}})$, is the associated relation.

Recall that any non-binary CSP instance can be converted into an equivalent binary instance by using dual encoding or hidden-variable transformation [23, 24]. In this paper, we consider only binary CSP instances, defined formally as follows:

Definition 2 (Binary CSP instance)

A binary CSP instance is a pair $I=(X,C)$ with:

• X: a set of n variables denoted by $\{x_{1},...,x_{n}\}$. Each variable $x_{i}$ has a domain $D(x_{i})$ containing at most d values.

• C: a set of e binary constraints. Each binary constraint $C_{ij}$ (with $i \neq j$) is a pair $(Scp(C_{ij}),Rel(C_{ij}))$ where:

  • $Scp(C_{ij}) = \{ x_{i},x_{j} \} \subseteq X$, is the scope of $C_{ij}$, i.e. a set of two variables involved by the constraint.

  • $Rel(C_{ij}) \subseteq D(x_{i}) \times D(x_{j})$, is the associated relation, a set of compatible pair of values called tuples.

If the constraint $C_{ij}$ is not defined in C, then we consider $C_{ij}$ to be a universal constraint (i.e. such that $Rel(C_{ij}) = D(x_{i}) \times D(x_{j})$).

Given a binary CSP instance $I = (X,C)$, an assignment of values to $Y\subseteq X$ is a set of pairs $\{(x_{i},v_{i})\mid x_{i}\in Y\}$ with $v_{i} \in D(x_{i})$ and $1 \leq i \leq n$, denoted generally (v₁,...v_k). A partial solution of $Y = \{x_{\ell _{1}},\ldots ,x_{\ell _{m}}\}$ is an assignment $\mathcal {A}= (v_{\ell _{1}},\ldots ,v_{\ell _{m}})\in D(x_{\ell _{1}})\times {\ldots } \times D(x_{\ell _{m}})$ which satisfies all constraints $C_{ij}$ such that $\{x_{i},x_{j}\} \subseteq Y$. A partial solution $\mathcal {A}$ is said to be complete solution (or solution for short) if $Y= X$ i.e. if

• $\mathcal {A}$ contains a value to each variable in X

• no pair of values of $\mathcal {A}$ violates any constraint of C

Given a CSP instance I, deciding whether I has a solution is well known to be NP-complete even for binary CSPs. Neverthless, there are some cases for which solving can be realized in polynomial time. In this case we speak about tractable classes. For example, BTP (for Broken-Triangle Property [11]) represents an important tractable class from a solving viewpoint as well as reduction operations viewpoint. BTP requires the absence of broken-triangles with respect to a given variable ordering. Formally, it is defined as follows:

Definition 3 (Broken-Triangle Property 10, 11)

Given a binary CSP instance I with a variable order $<$. A pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ satisfies BTP if, for each pair of variables $(x_{i},x_{j})$ (with $i \neq j \neq k$) such that, $\forall v_{i} \in D(x_{i})$, $\forall v_{j} \in D(x_{j})$, if

• $(v_{i},v_{j}) \in Rel(C_{ij})$,

• $(v_{i},v^{\prime }_{k}) \in Rel(C_{ik})$ and

• $(v_{j},v^{\prime \prime }_{k}) \in Rel(C_{jk})$,

then

• either $(v_{i},v^{\prime \prime }_{k}) \in Rel(C_{ik})$

• or $(v_{j},v^{\prime }_{k}) \in Rel(C_{jk})$.

A variable $x_{k}$ satisfies BTP if each pair of values in $D(x_{k})$ satisfies BTP. The instance I satisfies BTP with respect to $<$ if for all variables $x_{k}$, $x_{k}$ satisfies BTP in the sub-instance of I on variables $x_{i} \leq x_{k}$.

If $(v_{i},v^{\prime \prime }_{k}) \notin Rel(C_{ik})$ and $(v_{j},v^{\prime }_{k}) \notin Rel(C_{jk})$, we say that ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$) constitute a broken-triangle on the values $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ (or more generally on $x_{k}$).

Graphically, BTP can be represented in the micro-structure¹ [25] of I as shown in Fig. 1. For each pair of values $(v_{i},v_{j})$ (with $v_{i} \in D(x_{i})$, $v_{j} \in D(x_{j})$ and $i \neq j$), a solid line will be used to connect $v_{i}$ and $v_{j}$ if they are compatible (i.e. $(v_{i},v_{j}) \in Rel(C_{i j})$), a dotted line if they are incompatible (i.e. $(v_{i},v_{j}) \notin R_{ij}$), or no line if $(v_{i},v_{j})$ is an undefined tuple (i.e. a tuple which can be valid or invalid).

Fig. 1

The assignments ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$) form a broken-triangle in (a) but do not in (b)

Considering the variable ordering $x_{i} < x_{j} < x_{k}$, the CSP instance of Fig. 1a is not BTP because of the incompatibility of $(v_{j},v^{\prime }_{k})$ and $(v_{i},v^{\prime \prime }_{k})$. Thus, ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$) constitute a broken-triangle. In Fig. 1b, $(v_{i},v^{\prime \prime }_{k}) \in Rel(C_{ik})$ and $(v_{j},v^{\prime }_{k}) \in Rel(C_{jk})$, then the BTP is satisfied. The set of binary CSP instances which satisfy BTP constitutes a tractable class solved by enforcing Arc Consistency.

Definition 4

[2] Given a binary CSP instance $I=(X,C)$, a value $v_{i} \in D(x_{i})$ is arc-consistent with respect to $C_{ij} \in C$ if and only if there exists a value $v_{j} \in D(x_{j})$ such that $(v_{i},v_{j}) \in Rel(C_{ij})$. A domain $D(x_{i})$ is arc-consistent with respect to $Rel(C_{ij})$ if and only of $\forall v_{i} \in D(x_{i})$, the value $v_{i}$ is arc-consistent with respect to $Rel(C_{ij})$, and the binary CSP instance I is arc-consistent if and only if $\forall x_{i} \in X$, the domain $D(x_{i})$ is arc-consistent with respect to all $Rel(C_{ij})$ such that $C_{ij} \in C$.

Enforcing arc consistency consists of removing any value that is not arc-consistent. After enforcing arc consistency, if no domain has been wipped out, the binary CSP instance is consistent otherwise it is inconsistent. We have to mention that enforcing arc consistency preserves equivalence (and also satisfiability)

We now define value merging and variable elimination operations.

Definition 5

[5, 6] Merging the values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ in a binary CSP instance I consists of replacing $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ by a new value $v_{k}$ which is compatible with all values which are compatible with either $v^{\prime }_{k}$ or $v^{\prime \prime }_{k}$. A value-merging condition is a polytime-computable property such that when it holds on a pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$, the instance obtained after merging the values $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ is satisfiable if and only if I was satisfiable.

Definition 6

[7, 8] Eliminating a variable $x_{k}$ in a binary CSP instance $I=(X,C)$ consists of replacing X by $X \setminus \{x_{k}\}$ and C by $C \setminus \{C_{ik} \in C \mid i \neq k \}$. A variable-elimination condition is a polytime-computable property such that when it holds on a variable $x_{k}$, the instance obtained after eliminating $x_{k}$ is satisfiable if and only if I was satisfiable.

In [8], it has been shown that if there is no broken-triangle on each pair of values of a given variable $x_{k}$ in an arc-consistent binary CSP instance I, then $x_{k}$ can be eliminated from I without changing the satisfiability. For example, the variable $x_{k}$ of Fig. 1b can be eliminated while preserving satisfiability, contrary to $x_{k}$ of Fig. 1a.

In [6], the authors have proved that even when this rule cannot be applied because of the presence of some broken-triangles, it is possible that there is a pair of values $v^{\prime }_{k},v^{\prime \prime }_{k}$ in $D(x_{k})$ which satisfies BTP. In this case, these two values are mergeable. For example, in Fig. 1b, the values $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ are mergeable.

More recently, [19] showed that even when some broken-triangles are present on a pair of values $v^{\prime }_{k},v^{\prime \prime }_{k}$ which satisfies m-wBTP, merging $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ does not affect the satisfiability. Formally, m-wBTP is defined as follows:

Definition 7 (Weakly Broken-Triangle Property [19])

A pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ satisfies m-wBTP where $m \leq n-3$ if for each broken-triangle $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ with $v_{i} \in D(x_{i})$ and $v_{j} \in D(x_{j})$, there is a set of $r \leq m$ support variables $\{x_{\ell _{1}},\ldots ,x_{\ell _{r}}\} \subseteq X \setminus \{x_{i},x_{j},x_{k}\}$ such that for all $(v_{\ell _{1}},\ldots ,v_{\ell _{r}})\in D(x_{\ell _{1}})\times {\ldots } \times D(x_{\ell _{r}})$, if $(v_{\ell _{1}},\ldots ,v_{\ell _{r}},v_{i},v_{j})$ is a partial solution, then there is $\alpha \in \{1,\ldots ,r\}$ such that $(v_{\ell _{\alpha }},v^{\prime }_{k}), (v_{\ell _{\alpha }},v^{\prime \prime }_{k}) \notin Rel(C_{\ell _{\alpha } k})$.

Graphically, this definition can be represented through the micro-structure graph of Fig. 2. The pair $v^{\prime }_{k},v^{\prime \prime }_{k}$ satisfies 1-wBTP because the value $v_{\ell }$ in $D(x_{\ell })$ is compatible with both $v_{i}$ and $v_{j}$ but is not with $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$. So we say that the assignments $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ forms a weakly broken-triangle which is supported by $x_{\ell }$.

Fig. 2

A weakly broken-triangle $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ since $(v^{\prime }_{k},v_{\ell }),(v^{\prime \prime }_{k},v_{\ell }) \notin Rel(C_{k\ell })$

m-wBTP was designed primarily to merge a maximum number of values. This property seems to be very weak and it may be for this reason that it does not allow variable elimination (contrary to BTP) and it requires a high level of filtering by consistency to be polynomial. So, next section introduces the flexible broken-triangle concept which allows merging value and variable elimination while preserving satisfiability. Like m-wBTP, this new property will use the support variable concept but in a more restrictive way.

3 Flexible broken-triangles

A total absence of broken-triangles on a given variable in an arc-consistent CSP instance allows us to eliminate it without changing the satisfiability of the instance. In contrast, a total absence of weakly broken-triangles does not permit variable elimination.

Theoretically, we can define many examples of variables which can be eliminated despite the presence of certain broken-triangles while preserving satisfiability. As shown in the inconsistent CSP instance of Fig. 3, there is a broken-triangle on $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$, but after eliminating $x_{k}$ this CSP instance still remains inconsistent. So, the presence of some broken-triangle on a given variable does not preclude variable elimination while preserving satisfiability. For this, we introduce the flexible broken-triangles.

Fig. 3

The dashed variable x_k can be eliminated despite the presence of a broken-triangle

3.1 1-fBTP

Similar to m-wBTP, the m-fBTP is based on the concept of variable support. We begin by formally defining the simplest case (i.e. when $m = 1$).

Definition 8

A pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ satisfies 1-fBTP if for each broken-triangle ($v_{i},v_{j},v^{\prime }_{k},v^{\prime \prime }_{k}$) with v_i ∈ D(x_i), $v_{j} \in D(x_{j})$, then there is at least one variable $x_{\ell } \in X \setminus \{ x_{i},x_{j},x_{k}\}$ such that $\forall \ v_{\ell } \in D(x_{\ell })$, if (v_i,v_ℓ) ∈ Rel(C_iℓ) then $(v_{j},v_{\ell }) \notin Rel(C_{j \ell })$. If this is the case, ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$) is known as a flexible broken-triangle supported by the variable $x_{\ell }$. A variable $x_{k} \in X$ satisfies 1-fBTP if each pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ satisfies 1-fBTP.

In other words, each value in $D(x_{\ell })$ cannot be compatible with both $v_{i}$ and $v_{j}$ at the same time. If there is no variable $x_{\ell }$ which satisfies the previous conditions, then the pair $v^{\prime }_{k},v^{\prime \prime }_{k}$ does not satisfy 1-fBTP and ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$) will be called purely broken-triangle.

We specify that the broken-triangle in Fig. 3 is flexible because it is supported by the variable $x_{\ell }$ ((v_i,v_ℓ) ∈ Rel(C_iℓ), $(v_{j},v^{\prime }_{\ell }) \in Rel(C_{j \ell })$, $(v_{j},v_{\ell }) \notin Rel(C_{j \ell })$ and $(v_{i},v^{\prime }_{\ell }) \notin Rel(C_{j \ell })$).

We can intuitively deduce the following proposition:

Proposition 1

In a binary CSP instance $I=(X,C)$ , if a pair $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$ satisfies 1-fBTP, then it also satisfies 1-wBTP.

Proof

Straightforward. Indeed, to be 1-fBTP, we must have for each broken-triangle on $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ at least a support variable $x_{\ell }$ (for 1-fBTP) such that, each value $v_{\ell }$ in $D(x_{\ell })$ is not compatible with both $v_{i}$ and $v_{j}$ at the same time. Thus, we do not have to check the compatibility of $v_{\ell }$ with $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ because $x_{\ell }$ is also a support variable for 1-wBTP. Finally, the pair $v^{\prime }_{k}, v^{\prime \prime }_{k}\in D(x_{k})$ also satisfies 1-wBTP. □

The converse is obiously false by means of Fig. 2 where the pair $(v^{\prime }_{k},v^{\prime \prime }_{k})$ is 1-wBTP but is not 1-fBTP.

We immediately obtain the following result from Proposition 1 since m-wBTP allows value merging.

Corollary 1

In a binary CSP instance $I=(X,C)$ , merging a pair of values $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$ which satisfies 1-fBTP does not change the satisfiability of an instance.

In the rest of this subsection, support variable will refer to fBTP.

It is known that if for a given variable $x_{k}$ in an arc-consistent binary CSP instance I, the set of broken-triangles does not contain any pair of values $v^{\prime }_{k}, v^{\prime \prime }_{k}$ in $D(x_{k})$ with two assignments to two other variables, then the variable $x_{k}$ can be eliminated from I without modifying the satisfiability of I [8]. A similar result can also be shown for the variables satisfying 1-fBTP. To do it, we should prove the following lemma:

Lemma 1

Given a variable $x_{k}$ which satisfies 1-fBTP, after merging a pair of values $v^{\prime \prime }_{k}, v^{\prime \prime \prime }_{k} \in D(x_{k})$ into a new value $v^{\prime }_{k}$ , no purely broken-triangle can appear on $x_{k}$ .

Proof

We assume, for a contradiction, that after merging a pair of values $v^{\prime \prime }_{k}, v^{\prime \prime \prime }_{k}$ of a variable $x_{k}$ which satisfies 1-fBTP into a new value $v^{\prime }_{k}$, we introduced a new purely broken-triangle $(v_{k},v_{i},v_{j},v^{\prime }_{k})$. This can be translated into the following relations:

• (1) $(v_{i},v_{j}) \in Rel(C_{ij})$,

• (2) $(v_{i},v_{k}) \in Rel(C_{ik})$,

• (3) $(v_{j},v^{\prime }_{k}) \in Rel(C_{jk})$,

• (4) $(v_{j},v_{k}) \notin Rel(C_{jk})$ and

• (5) $(v_{i},v^{\prime }_{k}) \notin Rel(C_{ik})$.

By Definition 5, we also have: (5) $\Rightarrow$

• $(v_{i},v^{\prime \prime }_{k}) \notin Rel(C_{ik})$ (a) and

• $(v_{i},v^{\prime \prime \prime }_{k}) \notin Rel(C_{ik})$ (b).

(3) $\Rightarrow$

• either $(v_{j},v^{\prime \prime }_{k}) \in Rel(C_{jk})$ (c)

• or $(v_{j},v^{\prime \prime \prime }_{k}) \in Rel(C_{jk})$ (d).

(2), (1), (c), (a), and (4) $\Rightarrow$ a broken-triangle $(v_{i},v_{j},v_{k},v^{\prime \prime }_{k})$ and (2), (1), (d), (b) and (4) $\Rightarrow$ a broken-triangle $(v_{k},v_{i},v_{j},v^{\prime \prime \prime }_{k})$. In both cases, we had at least one broken-triangle before merging $v^{\prime \prime }_{k}$ and $v^{\prime \prime \prime }_{k}$. So, there is at least one variable $x_{\ell }$ such that for each value $v_{\ell } \in D(x_{\ell })$, if $(v_{i},v_{\ell }) \in Rel(C_{i \ell })$ then $(v_{j},v_{\ell }) \notin Rel(C_{j \ell })$. In this way, the variable $x_{\ell }$ also supports the broken-triangle $(v_{k},v_{i},v_{j},v^{\prime }_{k})$. Thus, $(v_{k},v_{i},v_{j},v^{\prime }_{k})$ is not a purely broken-triangle. But this contradicts our initial assumption. Therefore, merging two values $v^{\prime \prime }_{k}, v^{\prime \prime \prime }_{k}$ in the domain of a variable $x_{k}$ which satisfies 1-fBTP does not introduce a purely broken-triangle. □

We now establish the link with the variable elimination.

Theorem 1

Given an arc-consistent CSP instance $I=(X,C)$, if a variable $x_{k} \in X$ satisfies 1-fBTP, then it can be eliminated from I while preserving satisfiability.

Proof

Given an arc-consistent CSP instance $I=(X,C)$ and a variable $x_{k} \in X$ which satisfies 1-fBTP. As value merging makes no empty domain, we will merge each pair of values in D(x_k) until we obtain a unique value since (thanks to Lemma 1) merging a pair of values does not introduce a new purely broken-triangle on $x_{k}$. As I is arc-consistent, so any consistent assignment $\mathcal {A}$ to $X \backslash \{x_{k}\}$ can be easily extended to $x_{k}$ because $D(x_{k})$ contains a unique value and each value $\mathcal {A}[x_{i}]$ has a support in $D(x_{k})$. So, the unique value in $D(x_{k})$ is compatible with each value in $\mathcal {A}$. Thus, $x_{k}$ can be eliminated without changing the satisfiability of I. □

Like the majority of BTP extensions, the principle of support variable introduced for flexible broken-triangles can be expanded to more than one variable. This will allows us to capture more variables that can be eliminated in binary CSP instances and to define a maximal variable-elimination condition.

3.2 m-fBTP

We now enlarge the definition of flexible broken-triangle property by using m support variables. These variables guarantee the incompatibility of at least one of their value with at least one of two values $v_{i}$ and $v_{j}$ of the broken trinagle on $x_{k}$. From a micro-structure viewpoint, these variables prevent the emergence of a new clique² which did not exist previously (as shown in Fig. 4).

Fig. 4

Three different cases of two values $v^{\prime }_{k}$ and $v^{\prime \prime }_{k}$ which satisfy 2-fBTP.

We begin by formally defining m-fBTP.

Definition 9

A pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ satisfies m-fBTP where $m \leq n-3$ if for each broken-triangle $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ with $v_{i} \in D(x_{i})$ and $v_{j} \in D(x_{j})$, there is a set of $r \leq m$ support variables $\{x_{\ell _{1}},\ldots ,x_{\ell _{r}}\} \subseteq X \setminus \{x_{i},x_{j},x_{k}\}$ such that for all partial solution $(v_{\ell _{1}},\ldots ,v_{\ell _{r}})\in D(x_{\ell _{1}})\times {\ldots } \times D(x_{\ell _{r}})$, there is $\alpha \in \{1,\ldots ,r\}$ such that if $(v_{\ell _{\alpha }},v_{i}) \in Rel(C_{\ell _{\alpha } i})$, then $(v_{\ell _{\alpha }},v_{j}) \notin Rel(C_{\ell _{\alpha } j})$. In this case, we say that $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ is a flexible broken-triangle. A variable $x_{k} \in X$ satisfies m-fBTP if each pair of values $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$ satisfies m-fBTP.

As for 1-fBTP, if there is no set of m support variables which satisfies the previous conditions, then we will say that ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$) is a purely broken-triangle.

Three different configurations of Definition 9 are given in Fig. 4. In (a), there is no partial solution on the set of variables $\{x_{\ell _{\beta }},x_{\ell _{\gamma }}\}$. Hence $v^{\prime }_{k},v^{\prime \prime }_{k}$ in $D(x_{k})$ clearly satisfies 2-fBTP. In (b), the pair of values $v^{\prime }_{k},v^{\prime \prime }_{k}$ in $D(x_{k})$ satisfies 2-fBTP because for the two partial solutions $(v^{\prime }_{\ell _{\beta }},v^{\prime }_{\ell _{\gamma }})$ and $(v^{\prime \prime }_{\ell _{\beta }},v^{\prime \prime }_{\ell _{\gamma }})$, we have $(v^{\prime }_{\ell _{\gamma }},v_{j}) \notin Rel(C_{\ell _{\gamma } j} )$ and $(v^{\prime \prime }_{\ell _{\beta }},v_{i}) \notin Rel(C_{\ell _{\beta } i} )$. In (c), the pair of values $v^{\prime }_{k},v^{\prime \prime }_{k}$ in $D(x_{k})$ also satisfies 2-fBTP because for the two partial solutions $(v^{\prime }_{\ell _{\beta }},v^{\prime }_{\ell _{\gamma }})$ and $(v^{\prime \prime }_{\ell _{\beta }},v^{\prime \prime }_{\ell _{\gamma }})$, we have $(v^{\prime }_{\ell _{\gamma }},v_{j}) \notin Rel(C_{\ell _{\gamma } j} )$ and $(v^{\prime \prime }_{\ell _{\gamma }},v_{i}) \notin Rel(C_{\ell _{\gamma } i} )$. Obviously, these three examples are unsolvable (inconsistent). But it is possible to make them consistent by adding new solutions whose values are completely disjoint with the values present in the examples. Unfortunately, this will make the figures too dense and difficult to understand.

Note that in Fig. 4c, the variable $x_{\ell _{\gamma }}$ alone supports the broken-triangle $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$, so we can deduce that $x_{\ell _{\gamma }}$ and $x_{\ell _{\beta }}$ together support it. In Fig. 4a and b, $x_{\ell _{\gamma }}$ and $x_{\ell _{\beta }}$ together support the broken-triangle $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ none of them alone support it. From this, one can easily deduce the following result:

Proposition 2

Given a binary CSP instance $I=(X,C)$, if a pair of values $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$ satisfies m-fBTP then it satisfies (m + 1)-fBTP (0 ≤ m ≤ n − 4).

We now generalize Proposition 1 to any pair of values satisfying m-fBTP.

Proposition 3

In a binary CSP instance $I=(X,C)$, $\forall m, \ 0 \leq m \leq n-4$, if a pair $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$ satisfies m-fBTP, then it also satisfies m-wBTP.

Proof

For each broken-triangle on $v^{\prime }_{k}, v^{\prime \prime }_{k}$, there is a set of $r \leq m$ (with $0 \leq m \leq n-3$) support variables $\{x_{\ell _{1}},\ldots ,x_{\ell _{r}}\} \subseteq X \setminus \{x_{i},x_{j},x_{k}\}$ such that for all partial solution $(v_{\ell _{1}},\ldots ,v_{\ell _{r}}) \in D(x_{\ell _{1}})\times {\ldots } \times D(x_{\ell _{r}})$, there is $\alpha \in \{1,\ldots ,r\}$ such that if $(v_{\ell _{\alpha }},v_{i}) \in Rel(C_{\ell _{\alpha } i})$, then $(v_{\ell _{\alpha }},v_{j}) \notin Rel(C_{\ell _{\alpha } j})$. So each value $v_{\ell _{\alpha }}$ in $D(x_{\ell _{\alpha }})$ cannot be compatible with $v_{i}$ and $v_{j}$ at the same time. Thus, there can be no partial solution $(v_{\ell _{1}},\ldots ,v_{\ell _{r}})$. As a result, the pair $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$ also satisfies m-wBTP. □

Corollary 2

In a binary CSP instance $I=(X,C)$, merging a pair of values $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$ which satisfies m-fBTP does not change the satisfiability of I.

If we denote by m-fBTP-merging the merging operation based on m-fBTP, we can deduce that 0-wBTP-merging [19] and 0-fBTP-merging correspond to BTP-merging defined in [6] since they are based on zero support variables. Since BTP-merging generalizes both neighborhood substitution [3] and virtual interchangeability [4] and m-fBTP-merging generalizes BTP-merging for all $m \geq 0$, we immediately obtain the following results:

Corollary 3

m-fBTP-merging generalizes neighborhood substitution and virtual interchangeability.

Corollary 4

m-fBTP-merging merges more values than BTP-merging and less than m-wBTP-merging.

It is known that if a given variable $x_{k}$ in an arc-consistent binary CSP instance I satisfies BTP then $x_{k}$ can be eliminated without modifying the satisfiability of I [8]. A similar result can also be shown for the variables satisfying m-fBTP. To do it, we should prove the following lemma:

Lemma 2

Given a variable $x_{k}$ which satisfies m-fBTP, after merging a pair of values $v^{\prime \prime }_{k}, v^{\prime \prime \prime }_{k} \in D(x_{k})$ into a new value $v^{\prime }_{k}$, no purely broken-triangle can appear on $x_{k}$.

Proof

We assume, for a contradiction, that after merging a pair of values $v^{\prime \prime }_{k}, v^{\prime \prime \prime }_{k}$ of a variable $x_{k}$ which satisfies m-fBTP into a new value $v^{\prime }_{k}$, we introduced a new purely broken-triangle $(v_{k},v_{i},v_{j},v^{\prime }_{k})$. So we have:

• (1) $(v_{i},v_{j}) \in Rel(C_{ij})$,

• (2) $(v_{i},v_{k}) \in Rel(C_{ik})$,

• (3) $(v_{j},v^{\prime }_{k}) \in Rel(C_{jk})$,

• (4) $(v_{j},v_{k}) \notin Rel(C_{jk})$ and

• (5) $(v_{i},v^{\prime }_{k}) \notin Rel(C_{ik})$.

By definition 5, we obtain:

• $(v_{i},v^{\prime \prime }_{k}) \notin Rel(C_{ik})$ (a),

• $(v_{i},v^{\prime \prime \prime }_{k}) \notin Rel(C_{ik})$ (b), and

• either $(v_{j},v^{\prime \prime }_{k}) \in Rel(C_{jk})$ (c) or $(v_{j},v^{\prime \prime \prime }_{k}) \in Rel(C_{jk})$ (d).

(2), (1), (c), (a), and (4) $\Rightarrow$ a broken-triangle $(v_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ and (2), (1), (d), (b) and (4) $\Rightarrow$ a broken-triangle $(v_{k},v_{i},v_{j},v^{\prime \prime \prime }_{k})$. In both cases, we had at least one broken-triangle before merging $v^{\prime \prime }_{k}$ and $v^{\prime \prime \prime }_{k}$. So, there is a set of $r \leq m$ support variables $\{x_{\ell _{1}},\ldots ,x_{\ell _{r}}\} \subseteq X \setminus \{x_{i},x_{j},x_{k}\}$ such that for all partial solution $(v_{\ell _{1}},\ldots ,v_{\ell _{r}})\in D(x_{\ell _{1}})\times {\ldots } \times D(x_{\ell _{r}})$, there is $\alpha \in \{1,\ldots ,r\}$ such that if $(v_{\ell _{\alpha }},v_{i}) \in Rel(C_{ \ell _{\alpha } i})$, then $(v_{\ell _{\alpha }},v_{j}) \notin Rel(C_{\ell _{\alpha } j})$. In this way, the set of r support variables $\{x_{\ell _{1}},\ldots ,x_{\ell _{r}}\}$ also support the broken-triangle $(v_{k},v_{i},v_{j},v^{\prime }_{k})$. Thus, $(v_{k},v_{i},v_{j},v^{\prime }_{k})$ is not a purely broken-triangle. But this contradicts our initial assumption. Finally, merging two values $v^{\prime \prime }_{k}, v^{\prime \prime \prime }_{k}$ in the domain of a variable $x_{k}$ which satisfies m-fBTP does not introduce a purely broken-triangle. □

Lemma 2 cannot be extended to all pair of values which satisfies m-wBTP (and does not satisfy m-fBTP) [19]. Indeed, Fig. 5a illustrates the case of a variable $x_{4}$ which satisfies 1-wBTP since the variable $x_{3}$ supports all the broken-triangles on $x_{4}$. Figure 5b is obtained after merging the values 2 and 1 into a new value 3. Hence, the variable $x_{3}$ no longer support the broken-triangle $(3,2,2,0)$ (in bold) because the value $2 \in D(x_{3})$ is compatible at the same time with 2 $(\in D(x_{1}))$, 2 $(\in D(x_{2}))$ and 3 $(\in D(x_{4}))$.

Fig. 5

a A variable x₄ which satisfies 1-wBTP in an arc-consistent CSP instance. b The CSP instance obtained from I after merging the values 1 and 2 into a new value 3

We now establish the link with variable elimination.

Theorem 2

Given an arc-consistent CSP instance $I=(X,C)$, if a variable $x_{k} \in X$ satisfies m-fBTP, then it can be eliminated from I while preserving satisfiability.

Proof

Given an arc-consistent binary CSP instance $I=(X,C)$ and a variable $x_{k} \in X$ which satisfies m-fBTP. Since value merging makes no empty domain and does not affect the satisfiability of I (thanks to Corollary 2, we will merge each pair of values in $D(x_{k})$ until obtaining a unique value since merging a pair of values does not introduce a new purely broken-triangle on $x_{k}$ (thanks to Lemma 2).

As I is arc-consistent, so any consistent assignment $\mathcal {A}$ to $X \backslash \{x_{k}\}$ can be consistenly extended to $x_{k}$ because $D(x_{k})$ contains a unique value and each value $\mathcal {A}[x_{i}]$ has a support in $D(x_{k})$. So, the unique value in $D(x_{k})$ is compatible with each value in $\mathcal {A}$. Thus, $x_{k}$ can be eliminated without changing the satisfiability of I. □

4 A maximal variable-elimination condition

It has been proved that the variable which satisfies BTP can be eliminated while preserving satisfiability [8]. In Section 3, we have shown that even if a variable does not satisfy BTP it can be eliminated without changing the satisfiability of the instance while this variable satisfies m-fBTP. Thus, in an obvious sense, satisfying BTP is not a maximal variable-elimination condition.

Definition 10

A variable-elimination condition is maximal if the elimination of any other variable not respecting the condition necessarily leads to a modification of the satisfiability of some instance.

In this section, we show that m-fBTP is a maximal variable-elimination condition when $m=n-3$.

Theorem 3

In an unsatisfiable binary CSP instance $I=(X,C)$, there is no variable not satisfying m-fBTP for $m=n-3$ and which can be eliminated while preserving satisfiability.

Proof

Considering an unsatisfiable binary CSP instance $I=(X,C)$ and a variable $x_{k}$ which does not satisfy m-fBTP for $m=n-3$. By the definition of m-fBTP, there is a broken-triangle ($v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k}$), with $v_{i} \in D(x_{i})$, $v_{j}\in D(x_{j})$ and $v^{\prime }_{k},v^{\prime \prime }_{k} \in D(x_{k})$. And there is $(v_{\ell _{1}},\ldots ,v_{\ell _{m}}) \in D(x_{\ell _{1}})\times {\ldots } \times D(x_{\ell _{m}})$, where $\{x_{\ell _{1}},\dots ,x_{\ell _{m}}\} = X \setminus \{ x_{i},x_{j},x_{k}\}$, such that $(v_{\ell _{1}},\ldots ,v_{\ell _{m}})$ is a partial solution and for all $\alpha \in \{1,\ldots ,m\}$ we have:

• $(v_{\ell _{\alpha }},v_{i}) \in Rel(C_{\ell _{\alpha } i})$ and

• $(v_{\ell _{\alpha }},v_{j}) \in Rel(C_{\ell _{\alpha } j})$

In terms of micro-structure we have a $(n-1)$-clique (a subset of $n-1$ vertices that induces a complete subgraph) that we denote $Cl$. We have a broken-triangle, and so:

• $(v_{i},v^{\prime \prime }_{k}) \notin Rel(C_{ik})$,

• $(v_{j},v^{\prime }_{k}) \notin Rel(C_{jk})$,

• $(v_{i},v^{\prime }_{k}) \in Rel(C_{ik})$ and

• $(v_{j},v^{\prime \prime }_{k}) \in Rel(C_{jk})$

After eliminating $x_{k}$, and by definition of elimination, the obtained instance $I^{\prime }$ has (n − 1) variables and its micro-structure contains the $(n-1)$-clique $Cl$. According to Property 2 in [25], $Cl$ corresponds to a solution of $I^{\prime }$. Thus, we introduced a solution which did not exist in the initial instance since $(v_{i},v^{\prime \prime }_{k}) \notin Rel(C_{ik})$ and $(v_{j},v^{\prime }_{k}) \notin Rel(C_{jk})$. It follows that the elimination of variable which does not satisfy m-fBTP does not preserve satisfiability. □

We can now deduce the desired result.

Corollary 5

(n − 3)-fBTP is a maximal variable-elimination condition.

5 m-fBTP: tractability and solving

In this section, we show the tractability of instances satisfying m-fBTP. Next, we prove that these instances will be efficiently solved by algorithms of the state-of-the-art like MAC (Maintaining Arc Consistency [20]) and RFL (Real Full Look-ahead [21]).

5.1 Tractability of m-fBTP instances

Contrary to k-BTP and m-wBTP which sometimes need a high level of consistency, we show that arc consistency is a decision procedure for m-fBTP. After defining m-fBTP for pair of values and variable, we now extend the definition to binary CSP instances.

Definition 11

A binary CSP instance I with a variable ordering $<$ satisfies m-fBTP relative to this order if for all variables $x_{k}$, each pair of values in $D(x_{k})$ satisfies m-fBTP in the sub-instance of I on variables $x_{i} \leq x_{k}$ (m ≤ n − 3).

We now prove that m-fBTP is conservative³ [11], m-fBTP holds even after enforcing any filtering consistency which only removes values from domains.

Lemma 3

m-fBTP with respect to any fixed variable ordering is conservative.

Proof

It is clear that m-fBTP holds for a binary CSP instance thanks to the absence of some tuples. Obviously, removing values from the domain of any variable in a binary CSP instance cannot add new tuples. Thus, m-fBTP still holds. □

We now investigate the consequence of Lemma 3 on m-fBTP instances solving.

Theorem 4

Arc consistency is a decision procedure for any binary CSP instance which satisfies m-fBTP (1 ≤ m ≤ n − 3).

Proof

Let $I=(X,C)$ be a binary CSP instance satisfying m-fBTP with respect to a variable ordering $<$. We begin by enforcing arc consistency. If this results to an empty domain, then obviously the obtained instance has no solution. Otherwise, thanks to Lemma 3, we know that the obtained instance will also satisfy m-fBTP. According to Theorem 2, we can proceed iteratively to eliminate the last variable with respect to $<$ until obtaining an instance with three variables $x_{1}$, $x_{2}$ and $x_{3}$. As I is becoming arc-consistent, so there is no empty domain. Hence, $D(x_{1})$ (respectively $D(x_{2})$) must contain at least a value $v_{1}$ (resp. $v_{2}$) such that (v₁,v₂) ∈ Rel(C₁₂) (1). We will suppose, for a contradiction, that the assignment $\mathcal {A}=(v_{1},v_{2})$ cannot be consistenly extended to $x_{3}$. For this, we assume that there is no v₃ ∈ D(x₃) which is consistent with both $v_{1}$ and $v_{2}$. But, by arc consistency, we should have two values $v^{\prime }_{3}, v^{\prime \prime }_{3} \in D(x_{3})$ such that

• $(v_{1},v^{\prime }_{3}) \in Rel(C_{13})$ (2) and

• $(v_{2},v^{\prime }_{3}) \in Rel(C_{23})$ (3)

Note that $v^{\prime }_{3}$ and $v^{\prime \prime }_{3}$ must be different and $(v_{1},v^{\prime \prime }_{3}) \notin Rel(C_{13})$ (4) and $(v_{2},v^{\prime }_{3}) \notin Rel(C_{23})$ (5) (otherwise we contradict our hypothesis).

In this way, (1), (2), (3), (4) and (5) form a purely broken-triangle on $x_{k}$ which can be supported by no other variable. Indeed, by Definition 9, any variable x_ℓ must be different from $\{x_{i},x_{j},x_{k}\}$. Thus, this contradicts our assumption. Finally, $\mathcal {A}$ can be consistenly extended to $x_{3}$. □

The following theorem is a logical consequence of Corollary 5 and Theorem 4.

Theorem 5

The class of binary CSP instances which satisfy $(n-3)$ -fBTP defines the biggest tractable class resolved by variable elimination.

As with m-wBTP, checking whether it is possible to compute, in polynomial time, a variable ordering for which a binary CSP instance satisfies m-fBTP still remains an open question.

5.2 Solving of m-fBTP instances by algorithms of the state-of-the-art

BTP and m-fBTP share many interesting properties. For example, the two tractable classes are conservative and solved by arc consistency. Hence, as BTP is solved in polynomial time by MAC, we will prove that MAC and RFL solve m-fBTP instances in polynomial time as well. Recall that both MAC and RFL guarantee arc consistency at each node of the search tree. The difference between them is that MAC is developing a binary search tree and RFL is developing a search tree with at most d branches at each node of the search tree. In addition, MAC does not necessarily choose the same variable at each level of the search tree (see [26] for more details on backtrack algorithms).

Theorem 6

If a binary CSP instance I satisfies m-fBTP for an unknown variable ordering, then MAC and RFL solve I in polynomial time whatever the order of variables instanciation.

Proof

(Similar to the proof of Theorem 7.6. in [11]) Given a binary CSP instance I which satisfies m-fBTP, we deduce by Lemma 3 that any sub-instance of I, obtained after assigning a value v to a variable x, is also m-fBTP. By applying AC, the instance I either has a solution or has at least an empty domain. If there is an empty domain, then I is unsatisfiable. Otherwise (if there is no empty domain), MAC or RFL will find at least one value in the domain (which is non-empty) of the next variable which will be compatible with all the values in the current assignment. In the worst case, MAC or RFL will check the compatibility of the d values (in the domain of the next variable) with the current assignment in each level of the search tree. This operation will take $O(nd)$. Thus, MAC and RFL will have a complexity $O(ned^{3})$ with $O(ed^{2})$ for enforcing arc consistency after assigning a value to the current variable. □

5.3 What about variable ordering?

To check whether a given binary CSP instance I satisfies BTP, Cooper et al. in [11] propose to construct a new CSP instance $O^{I}$ which will be satisfiable when there exists a variable ordreing for I. $O^{I}$ has the same set of variables as I but with different domains. Indeed, each variable has n values representing its possible positions in the ordering. For each broken-triangle $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ in I with $v_{i} \in D(x_{i})$, $v_{j} \in D(x_{j})$ and $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$, there is a constraint c in $O^{I}$ over $x_{i}$, $x_{j}$ and $x_{k}$ which requires that $x_{k} < max(x_{i},x_{j})$. The instance $O^{I}$ is max-closed [27] and so is tractable (see proof of Theorem 3.2. in [11] for more details).

For m-fBTP, we will proceed in a somewhat similar way. If there is a purely broken-triangle on a given variable $x_{k}$ with respect to $x_{i}$ and $x_{j}$, we add a new constraint c to $O^{I}$ over $x_{i}$, $x_{j}$ and $x_{k}$ which requires that $x_{k} < max(x_{i},x_{j})$. And when there is a flexible broken-triangle on $x_{k}$ with respect to $x_{i}$ and x_j and which is supported by a variable $x_{\ell }$, we have to add a less restrictive constraint which requires that If $x_{k} > max(x_{i},x_{j})$ then x_ℓ < max(x_i,x_j). This constraint will guarantee that $x_{\ell }$ is before $x_{k}$ when $x_{k}$ is after $x_{i}$ and $x_{j}$ in the variable ordering, as mentioned in Definition 11. In other words, if two variables $x_{i}$ and $x_{j}$ form a flexible broken-triangle on $x_{k}$ and $x_{k} > max(x_{i},x_{j})$, the support variable $x_{\ell }$ must be before $x_{i}$ or $x_{j}$, otherwise $x_{k}$ does not satisfy 1-fBTP in the sub-instance of I on variables $x_{i} \leq x_{k}$.

Similarly, if the flexible broken-triangle on $x_{k}$ with respect to $x_{i}$ and $x_{j}$ and which is supported by a set of support variables $\{x_{\ell _{1}},x_{\ell _{2}},\ldots ,x_{\ell _{m}}\} \subseteq X \setminus \{x_{i},x_{j},x_{k}\}$, we have the following constraint which requires that If x_k > max(x_i,x_j) then $x_{\ell _{1}} < max(x_{i},x_{j})$ and $x_{\ell _{2}} < max(x_{i},x_{j})$ and ... and $x_{\ell _{m}} < max(x_{i},x_{j})$.

Unfortunately, in this case, we do not know whether the instance $O^{I}$ is tractable because their constraints are no longer max-closed. So, the question of the variable ordering for which a binary CSP instance satisfies m-fBTP still remains open.

Before concluding this section, we have to point out that, even if all the broken-triangles of a given binary CSP instance I are flexible, then I does not necessarily satisfy m-fBTP. Figure 6 shows the case of a binary CSP instance which does not satisfy 1-fBTP although all broken-triangles, listed below, are flexible.

• $(v^{\prime }_{i},v_{\ell },v_{k},v^{\prime \prime }_{i})$, $(v^{\prime }_{i},v_{\ell },v^{\prime }_{j},v^{\prime \prime }_{i})$ and $(v^{\prime }_{i},v^{\prime \prime }_{j},v_{k},v^{\prime \prime }_{i})$ on $x_{i}$, supported by $x_{j}$, $x_{k}$ and $x_{\ell }$, respectively.

• $(v^{\prime }_{j},v_{\ell },v_{k},v^{\prime \prime }_{j})$, $(v^{\prime }_{j},v_{\ell },v^{\prime }_{i},v^{\prime \prime }_{j})$ and $(v^{\prime }_{j},v^{\prime \prime }_{i},v_{k},v^{\prime \prime }_{j})$ on $x_{j}$, supported by $x_{i}$, $x_{k}$ and $x_{\ell }$, respectively.

• $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$, $(v^{\prime }_{k},v_{i},v_{\ell },v^{\prime \prime }_{k})$ and $(v^{\prime }_{k},v^{\prime \prime }_{\ell },v_{j},v^{\prime \prime }_{k})$ on $x_{k}$, supported by $x_{\ell }$, $x_{j}$ and $x_{i}$, respectively.

• $(v^{\prime }_{\ell },v_{i},v_{j},v^{\prime \prime }_{\ell })$, $(v^{\prime }_{\ell },v_{i},v^{\prime }_{k},v^{\prime \prime }_{\ell })$ and $(v^{\prime }_{\ell },v^{\prime \prime }_{k},v_{j},v^{\prime \prime }_{\ell })$ on $x_{\ell }$, supported by $x_{k}$, $x_{j}$ and $x_{i}$, respectively.

These flexible broken-triangles impose the following constraints on the variable ordering:

• If $x_{i} > max(x_{k},x_{\ell })$ then $x_{j} < max(x_{k},x_{\ell })$

• If $x_{i} > max(x_{\ell },x_{j})$ then $x_{k} < max(x_{\ell },x_{j})$

• If $x_{i} > max(x_{k},x_{j})$ then $x_{\ell } < max(x_{k},x_{j})$

• If $x_{j} > max(x_{k},x_{\ell })$ then $x_{i} < max(x_{k},x_{\ell })$

• If $x_{j} > max(x_{\ell },x_{i})$ then $x_{k} < max(x_{\ell },x_{i})$

• If $x_{j} > max(x_{k},x_{i})$ then $x_{\ell } < max(x_{k},x_{i})$

• If $x_{k} > max(x_{i},x_{j})$ then $x_{\ell } < max(x_{i},x_{j})$

• If $x_{k} > max(x_{\ell },x_{i})$ then $x_{j} < max(x_{\ell },x_{i})$

• If $x_{k} > max(x_{\ell },x_{j})$ then $x_{i} < max(x_{\ell },x_{j})$

• If $x_{\ell } > max(x_{i},x_{j})$ then $x_{k} < max(x_{i},x_{j})$

• If $x_{\ell } > max(x_{\ell },x_{i})$ then $x_{j} < max(x_{k},x_{i})$

• If $x_{\ell } > max(x_{\ell },x_{j})$ then $x_{i} < max(x_{k},x_{j})$

Fig. 6

A binary CSP instance which does not satisfy 1-fBTP whereas all broken-triangles are flexible

Thus, it is impossible to find a variable ordering for which the instance satisfies 1-fBTP.

6 m-fBTP vs some tractable classes based on BTP

BTP defines an important tractable class which has deserved to be studied and extended in many previous works (as mentioned in the introduction). Thus, it is natural to compare m-fBTP to some of these extensions such as DBTP [15], $\forall \exists$-BTP [13], BTP^AC [14], k-BTP [17] and WBTP [18]. For each class, we will show if it is a equality relation, inclusion or intersection.

6.1 DBTP

The Dual Broken-Triangle Property is an extension of BTP to non-binary CSPs by using the dual encoding [28]. Even for binary case, DBTP is different from BTP and authorizes the presence of some broken-triangles which are forbidden by BTP.

Definition 12 (DBTP [15, 29])

A binary CSP instance I satisfies DBTP with respect to a constraint ordering $\prec$ if and only if the dual of I satisfies BTP with respect to $\prec$.

Graphically, DBTP can be modelized as well as BTP, it suffices to replace each value in the micro-structure by a pair of compatible values in the micro-structure of the dual⁴ [30]. For the simplicity of graphical representation, we will use $v_{i}v_{j}$ to denote the compatible pair of values $(v_{i},v_{j})$ in the figure of the micro-structure of the dual.

Theorem 7

m-fBTP and DBTP are incomparable.

Proof

The binary CSP instance I of Fig. 7 satisfies 1-fBTP with respect to the variable ordering $x_{\ell } < x_{k} < x_{i} < x_{j}$ despite the presence of the following flexible broken-triangles:

• $(v_{i},v_{j},v^{\prime }_{k},v^{\prime }_{i})$ on $x_{i}$, supported by $x_{\ell }$

• $(v^{\prime }_{j},v^{\prime }_{i},v^{\prime }_{k},v_{j})$ on $x_{j}$, supported by $x_{\ell }$

• $(v^{\prime \prime }_{k},v^{\prime }_{j},v^{\prime }_{i},v^{\prime }_{k})$ on $x_{k}$, supported by $x_{\ell }$

• $(v_{i},v_{\ell },v^{\prime }_{j},v^{\prime }_{i})$ on $x_{i}$, supported by $x_{k}$

• $(v^{\prime }_{j},v_{\ell },v_{i},v_{j})$ on $x_{j}$, supported by $x_{k}$

This imposes the following constraints on the variable ordering:

• If $x_{i} > max(x_{k},x_{j})$ then $x_{\ell } < max(x_{k},x_{j})$

• If $x_{j} > max(x_{k},x_{i})$ then $x_{\ell } < max(x_{k},x_{i})$

• If $x_{k} > max(x_{i},x_{j})$ then $x_{\ell } < max(x_{i},x_{j})$

• If $x_{i} > max(x_{\ell },x_{j})$ then $x_{k} < max(x_{\ell },x_{j})$

• If $x_{j} > max(x_{\ell },x_{i})$ then $x_{k} < max(x_{\ell },x_{i})$

Fig. 7

a The micro-structure and b the micro-structure of the dual of a binary CSP instance I which satisfies 1-fBTP with respect to the order x_ℓ < x_k < x_i < x_j but does not DBTP whatever the constraint ordering

At the same time, the micro-structure of the dual of I does not satisfy BTP on each of the following three constraints:

• $((v_{j},v^{\prime }_{k}),(v_{i},v_{j}),(v_{i},v^{\prime \prime }_{k}),(v^{\prime }_{j},v^{\prime \prime }_{k}))$ on $C_{j k}$,

• $((v^{\prime }_{i},v^{\prime }_{j}),(v^{\prime }_{j},v^{\prime \prime }_{k}),(v_{i},v^{\prime \prime }_{k}),(v_{i},v_{j}))$ on $C_{i j}$ and

• $((v_{i},v^{\prime \prime }_{k}),(v_{i},v_{j}),(v_{j},v^{\prime }_{k}),(v^{\prime }_{i},v^{\prime }_{k}))$ on $C_{i k}$.

So I does not satisfy DBTP.

On the other side, the binary CSP instance I of Fig. 8 does not satisfy 1-fBTP whatever the variable ordering because of the following broken-triangles:

• $(v_{i},v^{\prime \prime }_{k},v^{\prime }_{j},v^{\prime }_{i})$ on $x_{i}$,

• $(v_{j},v_{i},v^{\prime \prime }_{k},v^{\prime }_{j})$ on $x_{j}$ and

• $(v^{\prime }_{k},v^{\prime }_{i},v^{\prime }_{j},v^{\prime \prime }_{k})$ on $x_{k}$.

Fig. 8

a The micro-structure and b the micro-structure of the dual of a binary CSP instance which satisfies DBTP with respect to the order C_ij < C_ik < C_jk but does not 1-fBTP whatever the variable ordering

And there is no fourth variable that can support one of these broken-triangles. Futhermore, the micro-structure of the dual of I satisfies BTP with respect to the constraint ordering C_ij < C_ik < C_jk. So I satisfies DBTP.

□

Finally, we deduce that DBTP and 1-fBTP are incomparable. $\Box$ Obviously, the instance of Figs. 7 and 8 can be generalized to any $m > 1$ while maintaining the same logic.

6.2 ∀∃-BTP

∀∃-BTP is a tractable class, introduced by Cooper in [13], and allows the existence of some broken-triangles.

Definition 13 (∀∃-BTP)

A binary CSP instance I satisfies the property $\forall \exists$-BTP with respect to a variable ordering $<$ if, and only if, for each pair of variables $x_{i}$, $x_{k}$ such that $i < k$, $\forall v_{i} \in D(x_{i})$, $\exists v_{k} \in D(x_{k})$ such that $(v_{i},v_{k}) \in Rel(C_{ik})$ and $\forall x_{j}$ with $j < k$ and $j \neq i$, and $\forall v_{j} \in D(x_{j})$ and $\forall v^{\prime }_{k} \in D(x_{k})$, $(v_{i},v_{j}, v_{k}, v^{\prime }_{k})$ is not a broken-triangle on $x_{k}$ with respect to $x_{i}$ and $x_{j}$.

Theorem 8 defines the relationship between m-fBTP and $\forall \exists$-BTP.

Theorem 8

m-fBTP and $\forall \exists$-BTP are incomparable.

Proof

Figure 9 shows a binary CSP instance which satisfies $\forall \exists$-BTP but does not satisfy 1-fBTP because there is no fourth variable which can support the following broken-triangles:

• $(v^{\prime }_{i},v_{k},v_{j},v^{\prime \prime }_{i})$ on $x_{i}$,

• $(v^{\prime \prime }_{j},v_{i},v_{k},v^{\prime }_{j})$ on $x_{j}$ and

• $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ on $x_{k}$.

For the binary CSP instance of Fig. 8a, we can observe that it satisfies 1-fBTP but does not satisfy $\forall \exists$-BTP. □

Fig. 9

A binary CSP instance which satisfies ∀∃-BTP whatever the variable ordering but does not satisfy 1-fBTP

6.3 BTP^AC

The concept of hidden tractable class, obtained by applying some polynomial transformation, has been introduced in [14] to extend the power of already existing tractable classes. In this way, and for the case of BTP, the presence of several broken-triangles can be allowed, especially when a broken-triangle contains at least one inconsistent value. Here, we compare m-fBTP to the smallest hidden tractable class based on BTP, namely BTP^AC which is obtained by filtering by arc consistency.

Definition 14 (BTP^AC[[spiespace)

]14] A binary CSP instance I satisfies BTP^AC if it satisfies BTP after enforcing arc consistency.

We now establish the link between m-fBTP and BTP^AC.

Theorem 9

m-fBTP and BTP^AC are incomparable.

Proof

Despite the presence of the following broken-triangles:

• $(v^{\prime }_{i},v^{\prime \prime }_{k},v_{j},v_{i})$ on $x_{i}$,

• $(v_{j},v_{i},v^{\prime }_{k},v^{\prime }_{j})$ on $x_{j}$ and

• $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ on $x_{k}$.

Figure 10a shows an example of a binary CSP instance which satisfies BTP^AC (All broken-triangles will be removed after enforcing arc consistency) but does not 1-fBTP (because there is no support variable for all the broken-triangles).

• $(v_{i},v_{j},v^{\prime \prime }_{k},v^{\prime }_{i})$ on $x_{i}$ which cannot be supported by $x_{\ell }$ because $v_{\ell }$ is compatible with both $v_{j}$ and $v^{\prime \prime }_{k}$.

• $(v_{j},v_{i},v^{\prime }_{k},v^{\prime }_{j})$ on $x_{j}$ which cannot be supported by $x_{\ell }$ because $v_{\ell }$ is compatible with both $v_{i}$ and $v^{\prime }_{k}$.

• $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ on $x_{k}$ which cannot be supported by $x_{\ell }$ because $v_{\ell }$ is compatible with both $v_{i}$ and $v_{j}$.

Thus this instance does not satisfy 1-fBTP (and obviously m-fBTP).

Fig. 10

a A binary CSP instance which satisfies BTP^AC but does not 1-fBTP. b A binary CSP instance which satisfies 1-fBTP but does not BTP^AC

Figure 10b illustrates the case of a binary CSP instance which does not satisfy BTP^AC since each value in this instance is arc-consistent. On the other hand, this binary CSP instance satisfies 1-fBTP with respect to the variable ordering $x_{\ell } < x_{i} < x_{j} < x_{k}$ despite the presence of four broken-triangles (only one is flexible):

• $(v^{\prime }_{\ell },v_{j},v_{i},v_{\ell })$ on $x_{\ell }$,

• $(v^{\prime }_{i},v_{k},v_{\ell },v_{i})$ on $x_{i}$,

• $(v_{j},v^{\prime }_{\ell },v_{k},v^{\prime }_{j})$ on $x_{j}$ and

• $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ on $x_{k}$ which is supported by $x_{\ell }$

which imposes the following constraints on the variable ordering:

• $x_{\ell } < max(x_{i},x_{j})$,

• $x_{i} < max(x_{\ell },x_{k})$,

• $x_{j} < max(x_{\ell },x_{k})$,

• If $x_{k} > max(x_{i},x_{j})$ then $x_{\ell } < max(x_{i},x_{j})$.

Finally, BTP^AC and 1-fBTP are incomparable. □

6.4 k-BTP

k-BTP [17] is an extension of BTP which authorizes some specific broken-triangles. Formally, it is defined as follows.

Definition 15 (k-BTP)

A binary CSP instance I satisfies the k-BTP property for a given k $(2 \leq k < n)$ relative to a variable order $<$ if, for all subsets of variables $x_{i_{1}},x_{i_{2}},\dots ,x_{i_{k + 1}}$ such that $x_{i_{1}} < x_{i_{2}} < {\dots } < x_{i_{k + 1}}$, there is at least one pair of variables $(x_{i_{j}},x_{i_{j^{\prime }}})$ with $1 \leq j < j^{\prime } \leq k$ such that there is no broken-triangle on $x_{k + 1}$ relative to $x_{i_{j}}$ and $x_{i_{j^{\prime }}}$.

The binary CSP instances which satisfy k-BTP do not define a tractable class if they are not strong strong k-consistent⁵ [31].

Theorem 10

[17] Given a binary CSP instance I such that there exists a constant k with $2 \leq k < n$ for which I satisfies both strong k-consistency and k-BTP with respect to the variable ordering $<$. Then I is consistent and a solution can be found in polynomial time.

Theorem 11

m-fBTP and k-BTP are incomparable.

Proof

Contrary to k-BTP which needs the strong k-consistency to be tractable, m-fBTP defines by itself a tractable class (it does not require any level of consistency). So if we consider a binary CSP instance I which satisfies m-fBTP but is not strong k-consistent, then even if I satisfies the property k-BTP, it will not be in the tractable class defined by k-BTP because it is not strong k-consistent.

Figure 11 illustrates the case of a binary CSP instance which does not satisfy k-BTP whatever the variable ordering because of the presence of the following flexible broken-triangles:

• $(v_{i},v^{\prime }_{j},v^{\prime }_{k},v^{\prime \prime \prime }_{i})$ on $x_{i}$ which is supported by $x_{\ell }$,

• $(v_{i},v^{\prime }_{\ell },v^{\prime }_{k},v^{\prime \prime \prime }_{i})$ on $x_{i}$ which is supported by $x_{j}$,

• $(v_{j},v^{\prime \prime }_{i},v^{\prime \prime }_{k},v^{\prime \prime \prime }_{j})$ on $x_{j}$ which is supported by $x_{\ell }$,

• $(v_{j},v^{\prime \prime }_{i},v^{\prime \prime }_{\ell },v^{\prime \prime \prime }_{j})$ on $x_{j}$ which is supported by $x_{k}$,

• $(v_{k},v_{\ell },v^{\prime \prime }_{j},v^{\prime \prime \prime }_{k})$ on $x_{k}$ which is supported by $x_{i}$ and

• $(v_{\ell },v^{\prime \prime }_{j},v^{\prime }_{i},v^{\prime \prime \prime }_{\ell })$ on $x_{\ell }$ which is supported by $x_{\ell }$.

Each one of these flexible broken-triangles imposes the following constraints on the variable ordering:

• If $x_{i} > max(x_{k},x_{j})$ then $x_{\ell } < max(x_{k},x_{j})$,

• If $x_{i} > max(x_{k},x_{\ell })$ then $x_{j} < max(x_{k},x_{\ell })$,

• If $x_{j} > max(x_{i},x_{k})$ then $x_{\ell } < max(x_{i},x_{k})$,

• If $x_{j} > max(x_{i},x_{\ell })$ then $x_{k} < max(x_{i},x_{\ell })$,

• If $x_{k} > max(x_{j},x_{\ell })$ then $x_{i} < max(x_{j},x_{\ell })$ and

• If $x_{\ell } > max(x_{i},x_{j})$ then $x_{k} < max(x_{i},x_{j})$.

Thus, there is no possible variable ordering for which this binary CSP instance satisfies 1-fBTP. In contrast, this binary CSP instance satisfies the property 3-BTP. Obviously, for each tuple $(v_{p},v_{q})$ in this binary CSP instance with $p ,q \in \{i,j,k,\ell \}$ and $p \neq q$, we can add two values, one to $x_{g}$ and the second to $x_{h}$ withg≠h and $g ,h \in \{i,j,k,\ell \} \setminus \{p,q\}$ such that the qudruplet $(v_{p},v_{q},v_{g},v_{h})$ constitutes a partial solution. In this way, this binary CSP instance satisfies both 3-BTP and strong 3-consistency. □

Fig. 11

A Binary CSP instance which satisfies the property 3-BTP with respect to every possible variable ordering but does not satisfy 1-fBTP, whatever the variable ordering

6.5 WBTP

We finish this section with the recent tractable class called WBTP [18].

Definition 16 (WBTP)

A binary CSP instance equipped with an order $<$ on its variables satisfies WBTP (Weak Broken-Triangle Property) if for each triple of variables $x_{i} < x_{j} < x_{k}$ and for all $v_{i} \in D(x_{i})$, $v_{j} \in D(x_{j})$ such that $(v_{i},v_{j}) \in Rel(C_{ij})$, there is a variable x_ℓ < x_k such that when $v_{\ell } \in D(x_{\ell })$ is compatible with $v_{i}$ and $v_{j}$, then $\forall v_{k} \in D(x_{k})$, if

• $(v_{\ell },v_{k}) \in Rel(C_{\ell k})$

then

• $(v_{i},v_{k}) \in Rel(C_{ik})$ and

• $(v_{j},v_{k}) \in Rel(C_{jk})$

Theorem 12

1-fBTP $\subsetneq$ WBTP.

Proof

Obviously because both WBTP and 1-fBTP use a unique support variable and their condition depends only from $v_{i}$ and $v_{j}$. □

The converse of Theorem 12 is false by means of Fig. 12. In fact, the binary CSP instance satisfies WBTP (anyone of $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ supports all the broken-triangles) but does not satisfy 1-fBTP (more details will be given in the proof of Theorem 13).

Fig. 12

A binary CSP instance which is WBTP but is not 2-fBTP

Theorem 13

2-fBTP and WBTP are incomparable.

Proof

Figure 12 shows a binary CSP instance which satisfies WBTP with respect to the variable ordering $x_{\ell _{\beta }} < x_{\ell _{\gamma }} < x_{i} < x_{j} < x_{k}$ but does not satisfy 2-fBTP. More precisely, there are three purely broken-triangles:

• $(v_{i},v^{\prime \prime }_{j},v^{\prime \prime }_{k},v^{\prime \prime \prime }_{i})$ on $x_{i}$ which cannot be supported by neither $x_{\ell _{\beta }}$ nor $x_{\ell _{\gamma }}$ (nor $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ together) because $v^{\prime \prime }_{\ell _{\beta }}$ and $v^{\prime \prime }_{\ell _{\gamma }}$ are compatible with both $v^{\prime \prime }_{j}$ and $v^{\prime \prime }_{k}$.

• $(v_{j},v^{\prime \prime }_{i},v^{\prime }_{k},v^{\prime \prime \prime }_{j})$ on $x_{j}$ which cannot be supported by neither $x_{\ell _{\beta }}$ nor $x_{\ell _{\gamma }}$ (nor $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ together) because $v^{\prime \prime \prime }_{\ell _{\beta }}$ and $v^{\prime \prime \prime }_{\ell _{\gamma }}$ are compatible with both $v^{\prime \prime }_{i}$ and $v^{\prime }_{k}$.

• $(v_{k},v^{\prime }_{i},v^{\prime }_{j},v^{\prime \prime \prime }_{k})$ on $x_{k}$ which cannot be supported by neither $x_{\ell _{\beta }}$ nor $x_{\ell _{\gamma }}$ (nor $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ together) because $v^{\prime }_{\ell _{\beta }}$ and $v^{\prime }_{\ell _{\gamma }}$ are compatible with both $v^{\prime }_{i}$ and $v^{\prime }_{j}$.

Figure 13 illustrates the case of a binary CSP instance which does not satisfy WBTP but satisfies 2-fBTP with respect to the variable ordering $x_{\ell _{\beta }} < x_{\ell _{\gamma }} < x_{i} < x_{j} < x_{k}$ despite the presence of the following broken-triangles:

• $(v_{i},v_{j},v^{\prime \prime }_{k},v^{\prime }_{i})$ on $x_{i}$ which is supported by $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ together.

• $(v_{j},v_{i},v^{\prime }_{k},v^{\prime }_{j})$ on $x_{j}$ which is supported by $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ together.

• $(v^{\prime }_{k},v_{i},v_{j},v^{\prime \prime }_{k})$ on $x_{k}$ which is supported by $x_{\ell _{\beta }}$ and $x_{\ell _{\gamma }}$ together.

• $(v^{\prime }_{k},v^{\prime \prime }_{\ell _{\gamma }},v_{j},v^{\prime \prime }_{k})$ on $x_{k}$ which is supported by $x_{i}$.

• $(v^{\prime }_{\ell _{\gamma }},v^{\prime }_{\ell _{\beta }},v_{j},v^{\prime \prime }_{\ell _{\gamma }})$ on $x_{\ell _{\gamma }}$ which cannot be supported by neither $x_{i}$ nor $x_{k}$ (nor $x_{i}$ and $x_{k}$ together).

• $(v^{\prime }_{\ell _{\beta }},v_{i},v^{\prime \prime }_{\ell _{\gamma }},v^{\prime \prime }_{\ell _{\beta }})$ on $x_{\ell _{\beta }}$ which cannot be supported by neither $x_{j}$ nor $x_{k}$ (nor $x_{j}$ and $x_{k}$ together).

Fig. 13

A binary CSP instance which is 2-fBTP but is not WBTP

They will impose the following constraints on the variable ordering:

• If $x_{i} > max(x_{j},x_{k})$ then $x_{\ell _{\beta }} < max(x_{j},x_{k})$ and $x_{\ell _{\gamma }} < max(x_{j},x_{k})$.

• If $x_{j} > max(x_{i},x_{k})$ then $x_{\ell _{\beta }} < max(x_{i},x_{k})$ and $x_{\ell _{\gamma }} < max(x_{i},x_{k})$.

• If $x_{k} > max(x_{i},x_{j})$ then $x_{\ell _{\beta }} < max(x_{i},x_{j})$ and $x_{\ell _{\gamma }} < max(x_{i},x_{j})$.

• If $x_{k} > max(x_{j},x_{\ell _{\beta }})$ then $x_{i} < max(x_{j},x_{\ell _{\beta }})$.

• $x_{\ell _{\beta }} < max(x_{i},x_{\ell _{\gamma }})$.

• $x_{\ell _{\gamma }} < max(x_{j},x_{\ell _{\beta }})$.

By considering the variable ordering $x_{\ell _{\beta }} < x_{\ell _{\gamma }} < x_{i} < x_{j} < x_{k}$, this binary CSP instance satisfies 2-fBTP. □

In the same way, we can show the following result:

Theorem 14

for $m>1$, m-fBTP and WBTP are incomparable.

Figure 14 summarizes some relationship between tractable classes based on BTP. An arrow from $c_{1}$ to $c_{2}$ (resp. a dashed line between $c_{1}$ and $c_{2}$) means that $c_{1} \subsetneq c_{2}$ (resp. $c_{1}$ and $c_{2}$ are incomparable). Obviously, a two-way arrow indicates equality.

Fig. 14

Relationship between tractable properties based on BTP

Some of these relationships have been proved in this paper and some others in [14, 32]. For several hidden tractable classes, more details about filtering by consistency can be found in [33, 34].

7 Experimental trials

To test the existence of the property 1-fBTP, we we carried out an experimental study on all the binary benchmark instances of the 2008 international CSP solver competition⁶, namely the 3,795 binary CSP instances. Our algorithm is written in C+ + within our own CSP library. The experiments were performed on 8 Dell PowerEdge M820 blade servers with two processors (Intel Xeon E5-2609 v2 2.5 GHz and 32 GB of memory) under Linux Ubuntu 14.04.

Before applying our algorithm, we point out that we made each instance arc-consistent. As described in Section 5.3, we associate a non-binary CSP instance O to each benchmark. After that, we check, for each variable $x_{k}$, if there exists a broken-triangle on each pair of values $v^{\prime }_{k}, v^{\prime \prime }_{k} \in D(x_{k})$. Once a broken-triangle on $v^{\prime }_{k}, v^{\prime \prime }_{k}$ is found, we search over the other $n-3$ variables to see if there exists a variable $x_{\ell }$ which supports this broken-triangle. If we find one, we add a constraint which requires If $x_{k} > max(x_{i},x_{j})$ then $x_{\ell } < max(x_{i},x_{j})$. Otherwise, the broken-triangle on x_k, we add a new constraint c to O over $x_{i}$, $x_{j}$ and $x_{k}$ which requires that $x_{k} < max(x_{i},x_{j})$. Finally, we use MAC to check the satisfiability of the orginal instance. The previous result is tantamount to saying whether the original instance satisfies 1-fBTP.

We obtained results for 3,260 instances. Among them, 280 instances satisfies 1-fBTP, including 46 consistent instances. All these instances also satisfy BTP after enforcing arc-consistency and solving by MAC and RFL without backtrack (more details are given in [14]).

8 Conclusion

BTP relies on absence of broken-triangle to define an important tractable class and to allow reducing search space size through value merging or variable elimination. Recently, many new weaker versions of BTP, which authorize the presence of some broken-triangle like k-BTP, WBTP and m-wBTP, have been studied but none of them define tractable class and permit variable elimination and value merging simultaneously. Moreover, much of these versions, except WBTP, require a high level of consistency.

In this paper, we have proposed a new light version of BTP, called m-fBTP for flexible broken-triangle property. m-fBTP is based on support variable concept and permits to cover some imperfections of previous versions. More precisely, it allows value merging, represents a maximal variable-elimination condition and also defines a hybrid tractable class solved by arc consistency. m-fBTP is incomparable with the patterns described in [35] and which characterize tractable classes for CSPs defined by partially-ordered forbidden patterns and solved by arc consistency.

It would be interesting to generalize this family of definitions to non-binary CSPs. More generally, we have to study a new extension of BTP that is based on only three variables and which preserves its interesting characteristics.