text: One of the key research interests in the area of Constraint Satisfaction Problem (CSP) is to identify tractable classes of constraints and develop efficient solutions for them. In this paper, we introduce generalized staircase (GS) constraints which is an important generalization of one such tractable class found in the literature, namely, staircase constraints. GS constraints are of two kinds, down staircase (DS) and up staircase (US). We first examine several properties of GS constraints, and then show that arc consistency is sufficient to determine a solution to a CSP over DS constraints. Further, we propose an optimal O(cd) time and space algorithm to compute arc consistency for GS constraints where c is the number of constraints and d is the size of the largest domain. Next, observing that arc consistency is not necessary for solving a DSCSP, we propose a more efficient algorithm for solving it. With regard to US constraints, arc consistency is not known to be sufficient to determine a solution, and therefore, methods such as path consistency or variable elimination are required. Since arc consistency acts as a subroutine for these existing methods, replacing it by our optimal O(cd) arc consistency algorithm produces a more efficient method for solving a USCSP.
  @cite_31: Many interesting tractable problems are identified under the model of Constraint Satisfaction Problems. These problems are usually solved by forcing a certain level of local consistency. In this paper, for the class of connected row convex constraints, we propose a novel algorithm which is based on the ideas of variable elimination and efficient composition of row convex and connected constraints. Compared with the existing work including randomized algorithms, the new algorithm has better worst case time and space complexity.
  @cite_8: This paper studies constraint satisfaction over connected row-convex (CRC) constraints. It shows that CRC constraints are closed under composition, intersection, and transposition, the basic operations of path-consistency algorithms. This establishes that path consistency over CRC constraints produces a minimal and decomposable network and is thus a polynomial-time decision procedure for CRC networks. This paper also presents a new path-consistency algorithm for CRC constraints running in time O(n(3)d(2)) and space O(n(2)d), where n is the number of variables and d is the size of the largest domain, improving the traditional time and space complexity by orders of magnitude. The paper also shows how to construct CRC constraints by conjunction and disjunction of a set of basic CRC constraints, highlighting how CRC constraints generalize monotone constraints and presenting interesting subclasses of CRC constraints. Experimental results show that the algorithm behaves well in practice. (C) 1999 Elsevier Science B.V. All rights reserved.
summary: GS constraints are a subclass of CRC constraints. While path consistency is sufficient to solve a CSP over CRC constraints, we show that arc consistency is sufficient to solve a CSP over DS constraints (please refer to Theorem ). However, it is not known that whether US constraints are solvable using arc consistency. For the class of CRC constraints, a path consistency based algorithm was proposed in @cite_8 that runs in @math time. Based on variable-elimination, @cite_31 stated an @math time algorithm for CRC constraints where @math is the degree of elimination of the triangulated graph of the underlying constraint network. Both these algorithms for CRC constraints use arc consistency as a subroutine which takes @math time. US constraints being a subclass of CRC constraints can be solved by either of these techniques mentioned above. Our arc consistency algorithm for GS constraints that runs in @math time, acting as a subroutine, thus improves the time complexity of the algorithm by @cite_31 to @math (which is linear in @math ), when applied to US constraints.