On Binary Constraint Networks

Abstract

It is well-known that general constraint satisfaction problems (CSPs) may be reduced to the binary case (BCSPs) [Pei92]. CSPs may be represented by binary constraint networks (BCNs), which can be represented by a graph with nodes for variables for which values are to be found in the domain of interest, and edges labelled with binary relations between the values, which constrain the choice of solutions to those which satisfy the relations (e.g. [Mac77]). We formulate networks and algorithms in a general algebraic setting, that of Tarski's relation algebra [JonTar52], and obtain a parallel O(n log n) upper bound for path-consistency, and give a class of examples on which reduction-type algorithms (which include the standard serial algorithms [Mac77, MacFre85, MohHen86] and all possible parallelisations of them) are O(n ). We then consider BCNs over various classes of relations that arise from an underlying linearly ordered set, the most well-known being the interval algebra [All83, LadMad88.1]. There are three main consequences of the algebraic approach. Firstly, it puts the theory of BCNs on a firm (and classical) theoretical footing, enabling, for example, the complexity results. Secondly, we can apply techniques from relation algebra to show that consistency checking for a large class of relations on intervals ([All83]) is serial cubic, or parallel log time, significantly extending previous results (the problem is NP-hard in general [VilKau86]). Thirdly, results are obtained via a new construction of relation algebras from other algebras which is of independent mathematical interest.