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.
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.
@cite_31 @cite_8
1590901743 1985525233
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. We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints. Analogously we represent the positive disjunctive constraints by a so-called forcing graph. For conflict graphs we prove that the maximum flow problem is strongly @math -hard, even if the conflict graph consists only of unconnected edges. This result still holds if the network consists only of disjoint paths of length three. For forcing graphs we also provide a sharp line between polynomially solvable and strongly @math -hard instances for the case where the flow values are required to be integral. Moreover, our hardness results imply that no polynomial time approximation algorithm can exist for both problems. In contrast to this we show that the maximum flow problem with a forcing graph can be solved efficiently if fractional flow values are allowed. Let @math be a nontrivial @math -ary predicate. Consider a random instance of the constraint satisfaction problem @math on @math variables with @math constraints, each being @math applied to @math randomly chosen literals. Provided the constraint density satisfies @math , such an instance is unsatisfiable with high probability. The problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate @math supports a @math - probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree @math (which runs in time @math ) refute a random instance of @math . In particular, the polynomial-time SOS algorithm requires @math constraints to refute random instances of CSP @math when @math supports a @math -wise uniform distribution on its satisfying assignments. Together with recent work of [LRS15], our result also implies that polynomial-size semidefinite programming relaxation for refutation requires at least @math constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate @math , they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of [AOW15] and [RRS16], this full three-way tradeoff is , up to lower-order factors. Many real-life Constraint Satisfaction Problems (CSPs) involve some constraints similar to the alldifferent constraints. These constraints are called constraints of difference. They are defined on a subset of variables by a set of tuples for which the values occuring in the same tuple are all different. In this paper, a new filtering algorithm for these constraints is presented. It achieves the generalized arc-consistency condition for these non-binary constraints. It is based on matching theory and its complexity is low. In fact, for a constraint defined on a subset of p variables having domains of cardinality at most d, its space complexity is O(pd) and its time complexity is O(p2d2). This filtering algorithm has been successfully used in the system RESYN ( 1992), to solve the subgraph isomorphism problem.