Dynamic algorithms for classes of constraint satisfaction problems

Many fundamental tasks in artificial intelligence and in combinatorial opti mization can be formulated as a constant Satisfaction Problem (CSP). It is the problem of finding an assignment of values for a set of variables, each defined on a finite domain of feasible values, subject to a given collecti on of constraints. Each constraint is defined over a set of variables and s pecifies the allowed combinations of values as a collection of tuples. In g eneral, the problem of finding a solution to a CSP is NP-complete, but in s ome cases it has shown to be polynomially solvable. We consider the dynamic version of some polynomially solvable constraint satisfaction problems, an d present solutions that are better than recomputing everything from scratc h after each update. The updates we consider are either restrictions, i.e., deletions of values from existing constraints and introduction of new cons traints, or relaxations, i.e., insertions of values or deletions of constra ints. (C) 2001 Elsevier Science B.V. All rights reserved.