text: Symmetry is a common feature of many combinatorial problems. Unfortunately eliminating all symmetry from a problem is often computationally intractable. This paper argues that recent parameterized complexity results provide insight into that intractability and help identify special cases in which symmetry can be dealt with more tractably.
  @cite_4: Abstract Finding solutions to a binary constraint satisfaction problem is known to be an NP-complete problem in general, but may be tractable in cases where either the set of allowed constraints or the graph structure is restricted. This paper considers restricted sets of constraints which are closed under permutation of the labels. We identify a set of constraints which gives rise to a class of tractable problems and give polynomial time algorithms for solving such problems, and for finding the equivalent minimal network. We also prove that the class of problems generated by any set of constraints not contained in this restricted set is NP-complete.
  @cite_33: 
  @cite_8: 
  @cite_36: We study the computational complexity of reasoning with global constraints. We show that reasoning with such constraints is intractable in general. We then demonstrate how the same tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when decomposing constraints will lose pruning, and when combining constraints is tractable. We also show how the same tools can be used to study symmetry breaking, meta-constraints like the cardinality constraint, and learning nogoods.
  @cite_42: Abstract The paper offers a systematic way of regrouping constraints into hierarchical structures capable of supporting search without backtracking. The method involves the formation and preprocessing of an acyclic database that permits a large variety of queries and local perturbations to be processed swiftly, either by sequential backtrack-free procedures, or by distributed constraint propagation processes.
  @cite_39: 486,344. Roller bearings. BENEDEK, E. K. March 15, 1937, No. 7567. [Class 12 (i)] A high-speed heavyload needle roller bearing comprises two races 7, 8, with needle rollers 31, the individual rollers being spaced apart by a lubricant film and the total clearance between the rollers of a set lying between the limits of one to three needle roller diameters whereby an efficient circulation of lubricant is obtained. As shown, for a multiple row bearing, one of the races has annular oil channels 6 and the other lubricant ducts 9. Rings 10 separate the rows of rollers. The needle rollers may be conical. The invention may be applied to single and double thrust bearings. In a modification needle rollers 3, Fig. 12, carried in a rectangular cage 16 are arranged between members 14, 15, having relative oscillatory or rotary motion. The total clearance between the rollers and the cage lies between one to three roller diameters. A rectilinear-motion bearing is constructed similarly. Specification 410,968 is referred to.
  @cite_19: We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain @math for each variable x, and a "cardinality set" K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption FPT???W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.
  @cite_5: 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.
  @cite_25: We generalize Krishnamurthy’s well-studied symmetry rule for resolution systems by considering homomorphisms instead of symmetries; symmetries are injective maps of literals whichpreserve complements and clauses; homomorphisms arise from symmetries by releasing the constraint of being injective. We prove that the use of homomorphisms yields a strictly more powerful system than the use of symmetries by exhibiting an infinite sequence of sets of clauses for which the consideration of global homomorphisms allows exponentially shorter proofs than the consideration of local symmetries. It is known that local symmetries give rise to a strictly more powerful system than global symmetries; we prove a similar result for local and global homomorphisms. Finally, we obtain an exponential lower bound for the resolution system enhanced by the local homomorphism rule.
summary: The study of computational complexity in constraint programming has tended to focus on the structure of the constraint graph (e.g. especially measures like tree width @cite_33 @cite_42 ) or on the semantics of the constraints (e.g. @cite_4 ). However, these lines of research are mostly concerned with constraint satisfaction problems as a whole, and do not say much about individual (global) constraints. For global constraints of bounded arity, asymptotic analysis has been used to characterize the complexity of propagation both in general and for constraints with a particular semantics. For example, the generic domain consistency algorithm of @cite_39 has an @math time complexity on constraints of arity @math and domains of size @math , whilst the domain consistency algorithm of @cite_5 for the @math -ary constraint has @math time complexity. Bessiere showed that many global constraints like are also intractable to propagate @cite_36 . More recently, Samer and Szeider have studied the parameterized complexity of the constraint @cite_19 . Szeider has also studied the complexity of symmetry in a propositional resolution calculus @cite_25 . See Chapter 10 in @cite_8 for more about symmetry of propositional systems.