A BTP-Based Family of Variable Elimination Rules 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 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.