A Hybrid Tractable Class for Non-binary CSPs
Achref El Mouelhi, Philippe Jégou, Cyril Terrioux · 2013
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.