Simple Randomized Algorithms for Tractable Row and Tree Convex Constraints

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

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.