Simple Randomized Algorithms for Tractable Row and Tree Convex Constraints

Abstract

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 (known) deterministic algorithms and the (generic) 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 pathconsistent networks.