Domain permutation reduction for constraint satisfaction problems

摘要

This paper is concerned with the Constraint Satisfaction Problem (CSP). It is well-known that the general CSP is NP-hard. However, there has been significant success in discovering subproblems which are tractable (polynomial time solvable). One of the most effective ways to obtain a tractable subproblem has been to force all of the constraint relations to lie in some tractable language.In this paper we define a new way of identifying tractable subproblems of the CSP. Let P be an arbitrary CSP instance and Γ be any tractable language. Suppose there exists, for each variable of P, a permutation of the domain such the resultant permuted constraint relations of P all lie in Γ. The domain permuted instance is then an instance of a tractable class and can be solved by the polynomial time algorithm for Γ. Solutions to P can be obtained by inverting the domain permutations.The question, for a given class of instances and language Γ, whether such a set of domain permutations can be found efficiently is the key to this method's tractability. One of the important contributions made in this paper is the notion of a “lifted constraint instance” which is a powerful tool to study this question.•We consider the open problem of discovering domain permutations which make instances max-closed. We show that, for bounded arity instances over a Boolean domain this problem is tractable, while for domain size three it is intractable even for binary instances.•We give a simple proof verifying the tractability of discovering domain permutations which make instances row convex. We refute a published result by giving a simple proof of the intractability of discovering domain permutations which make instances, even with domain size four, connected row convex.•We demonstrate that triangulated and stable marriage instances are reducible, via domain permutations, to max-closed instances. This provides a simple explanation for arc consistency deciding these instances.•We verify with a simple direct proof the tractability of identification of renamable Horn instances, and the intractability of finding the largest renamable Horn subset of clauses of an instance of SAT.•We describe natural tractable classes which properly extend the maximal relational classes arising from tractable constraint languages.We believe that domain permutation reductions have a significant chance of being useful in practical applications.