Extending the Broken Triangle Property tractable class of binary CSPs
Wady Naanaa · 2016
Finding a solution to a Constraint Satisfaction Problem, (CSP), is known to be an NP-complete task. This has motivated the multitude of works that have been devoted to identifying tractable classes of CSP. Tractability is obtained by imposing specific problem structures, specific relations between variables or both structural and relational properties. In the latter case, we obtain hybrid tractable CSP classes. This paper presents an extension of an existing hybrid tractable class of binary CSP named the weak broken-triangle property class. We provide a polynomial identification algorithm and a polynomial solution algorithm to process the instances in the proposed super-class. We also derive a new structural property, which, when owned by a n-ary CSP instance, ensures its tractability.