The Broken-Triangle Property with Adjoint Values

摘要

Recently, the Broken Triangle Property (BTP) and its extensions have been proposed to identify hybrid tractable classes of Constraint Satisfaction Problems (CSPs). In this paper, we extend the BTP to the concept of the Broken Triangle Property with adjoint values (BTPv), and then identify a more general hybrid tractable class of binary CSPs. To prove tractability, we present a polynomial-time algorithm to solve CSP instances in the new tractable class using a novel variable selection mechanism, and show correctness of it. We also show that determining whether an instance is in the class can be achieved efficiently. Furthermore, we provide comparisons with the BTP and its extensions showing that as a generalization of the BTP, the BTPv can find novel tractable CSPs, which cannot be identified by those existing tractable classes.