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.
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.
@cite_4 @cite_33 @cite_8 @cite_36 @cite_42 @cite_39 @cite_19 @cite_5 @cite_25
1748315421 2002478775 137416953 1999038767 1592840579 2123103890 2164279585 2905990799
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. The valued constraint satisfaction problem (VCSP) is an optimization framework originating from artificial intelligence which generalizes the classical constraint satisfaction problem (CSP). In this paper, we are interested in structural properties that can make problems from the VCSP framework, as well as other CSP variants, solvable to optimality in polynomial time. So far, the largest structural class that is known to be polynomial-time solvable to optimality is the class of bounded hypertree width instances introduced by Here, larger classes of tractable instances are singled out by using dynamic programming and structural decompositions based on a hypergraph invariant proposed by Grohe and Marx. In the second part of the paper, we take a different view on our optimization problems; instead of considering fixed arbitrary values for some structural invariant of the (hyper)graph structure of the constraints, we consider the problems parameterized by the tree-width of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. Such parameterizations of plain CSPs have been studied by Samer and Szeider. Here, we extend their framework to encompass our optimization problems, by coupling it with further non-trivial machinery and new reductions. By doing so, we are able to determine numerous combinations of the considered parameters that make our optimization problems admit fixed-parameter algorithms. We show that tools from circuit complexity can be used to study decompositions of global constraints. In particular, we study decompositions of global constraints into conjunctive normal form with the property that unit propagation on the decomposition enforces the same level of consistency as a specialized propagation algorithm. We prove that a constraint propagator has a a polynomial size decomposition if and only if it can be computed by a polynomial size monotone Boolean circuit. Lower bounds on the size of monotone Boolean circuits thus translate to lower bounds on the size of decompositions of global constraints. For instance, we prove that there is no polynomial sized decomposition of the domain consistency propagator for the ALLDIFFERENT constraint. 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. For certain subclasses of NP, @math P, or #P characterized by local constraints, it is known that if there exist any problems within that subclass that are not polynomial time computable, then all the problems in the subclass are NP-complete, @math P-complete, or #P-complete. Such dichotomy results have been proved for characterizations such as constraint satisfaction problems and directed and undirected graph homomorphism problems, often with additional restrictions. Here we give a dichotomy result for the more expressive framework of Holant problems. For example, these additionally allow for the expression of matching problems, which have had pivotal roles in the development of complexity theory. As our main result we prove the dichotomy theorem that, for the class @math P, every set of symmetric Holant signatures of any arities that is not polynomial time computable is @math P-complete. The result exploits some special properties of the class @math P and characterizes four distinct tractable ... We investigate the computational complexity of two global constraints, CUMULATIVE and INTERDISTANCE. These are key constraints in modeling and solving scheduling problems. Enforcing domain consistency on both is NP-hard. However, restricted versions of these constraints are often sufficient in practice. Some examples include scheduling problems with a large number of similar tasks, or tasks sparsely distributed over time. Another example is runway sequencing problems in air-traffic control, where landing periods have a regular pattern. Such cases can be characterized in terms of structural restrictions on the constraints. We identify a number of such structural restrictions and investigate how they impact the computational complexity of propagating these global constraints. In particular, we prove that such restrictions often make propagation tractable. We propose AllDiffPrecedence, a new global constraint that combines together an AllDifferent constraint with precedence constraints that strictly order given pairs of variables. We identify a number of applications for this global constraint including instruction scheduling and symmetry breaking. We give an efficient propagation algorithm that enforces bounds consistency on this global constraint. We show how to implement this propagator using a decomposition that extends the bounds consistency enforcing decomposition proposed for the AllDifferent constraint. Finally, we prove that enforcing domain consistency on this global constraint is NP-hard in general. We revisit the SeqBin constraint. This meta-constraint subsumes a number of important global constraints like Change, Smooth and IncreasingNValue. We show that the previously proposed filtering algorithm for SeqBin has two drawbacks even under strong restrictions: it does not detect bounds disentailment and it is not idempotent. We identify the cause for these problems, and propose a new propagator that overcomes both issues. Our algorithm is based on a connection to the problem of finding a path of a given cost in a restricted @math -partite graph. Our propagator enforces domain consistency in O(nd^2) and, for special cases of SeqBin that include Change, Smooth and IncreasingNValue, in O(nd) time. We study from a formal perspective the consistency and propagation of constraints involving multiset variables. That is, variables whose values are multisets. These help us model problems more naturally and can, for example, prevent introducing unnecessary symmetry into a model. We identify a number of different representations for multiset variables and compare them. We then propose a definition of local consistency for constraints involving multiset, set and integer variables. This definition is a generalization of the notion of bounds consistency for integer variables. We show how this local consistency property can be enforced by means of some simple inference rules which tighten bounds on the variables. We also study a number of global constraints on set and multiset variables. Surprisingly, unlike finite domain variables, the decomposition of global constraints over set or multiset variables often does not hinder constraint propagation.