language: en

Constraint Satisfaction Problem as a Causal Theory

Robert Rodosek
University of Munich, Department of Computer Science
Theresienstrae 39, 80333 Munich, Germany
rodosek@informatik.uni-muenchen.de

Abstract The aim of this paper is to identify and to characterize the features that render one class of the Constraint Satisfaction Problem (CSP) computationally more efficient. Our approach is to search for a causal structure not only in the topology of the subsets of variables upon which the constraints are specified, but also in the nature of the constraints. Basically, there should exist an ordering of variables in the system such that an assignment of the variables can be reached without backtracking. First, an approach of a causal structure is formulated, and second, an efficient procedure is provided (i) for deciding if such an ordering of variables exists and, (ii) for identifying such an ordering whenever possible.

1 Introduction