Simple Randomized Algorithms for Tractable Row and Tree Convex Constraints

T. K. Satish Kumar

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.

Subjects: 15.2 Constraint Satisfaction; 9.2 Computational Complexity

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.