Proceedings of the AAAI Conference on Artificial Intelligence, 21
Constraint Satisfaction and Satisfiability
We identify tractable classes of constraints based on the following simple property of a constraint: "At every infeasible point, there exist two directions such that with respect to any other feasible point, moving along at least one of these two directions decreases a certain distance metric to it". We show that connected row convex (CRC) constraints, arc-consistent consecutive tree convex (ACCTC) constraints, etc fit this characterization, and are therefore amenable to extremely simple polynomial-time randomized algorithms—the complexities of which are shown to be much less than that of the corresponding deterministic algorithms (when they exist) and/or the lower bounds for establishing path-consistency. On a related note, we also provide a simple polynomial-time deterministic algorithm for finding tree embeddings of variable domains (if they exist) for establishing tree convexity in path-consistent networks.