Reasoning about NP-complete Constraints

1 Introduction

Constraint programming (CP) has been a very successful framework for modeling and solving hard combinatorial problems. Many problems are naturally framed as constraint satisfaction or optimization problems, where a set of discrete valued variables is to be assigned while satisfying a set of constraints. For instance, CP has been successfully applied to managing the aftermath of natural disasters [Hentenryck, 2013], optimizing the delivery of radiotherapy in cancer treatment [Cambazard et al., 2012] or scheduling the exploration of a comet [Simonin et al., 2012].

A first strength of CP often put forward, is its declarative aspect. Another essential feature is the modularity and versatility of the inference mechanisms. The key principle is the notion of local consistency: if we can deduce that some assignments are locally infeasible, for instance with respect to a single constraint, then the same deduction holds globally. In particular, a constraint network is said domain 1 consistent [Waltz, 1975] when there is no further deduction to be made, with respect to any single constraint, about the possible values that its variables can take. It was shown that maintaining this level of consistency during search was often a good choice [Sabin and Freuder, 1994] and most constraint solvers are designed according to this principle.

1 Or equivalently arc consistent

The notion of global constraint makes this type of reasoning extremely powerful. A constraint is said global when it corresponds to a class of relations on an arbitrary number of variables. For instance, the constraint ALLDIFFERENT ensures that a set of variables take all pairwise distinct values. Given a recurring subproblem for which there exists an efficient algorithm, it is natural to derive the corresponding constraint, that is, design a propagation algorithm responsible for making deduction locally to that constraint. For instance, the propagation algorithm for the ALLDIFFERENT constraint [R´egin, 1994] is based on Hopcroft and Karp's maximum matching algorithm [Hopcroft and Karp, 1973]. Similarly, a number of constraints are propagated using results from flow theory [van Hoeve et al., 2006] or dynamic programming [Pesant, 2004; Hebrard et al., 2009].

Since constraints must be easily checkable, they lie within the complexity class NP. However, many recurring subproblems that might qualify as constraints are NPcomplete [Bessiere et al., 2006b]. Examples of NP-complete constraints are numerous. For instance for ensuring that a set of Boolean variables represent a clique of a certain size [Fahle, 2002; R´egin, 2003]; that integer variables representing vertices of a graph are given a value corresponding to an isomorphic vertex in a larger graph [R´egin, 1995]; that the least and highest number of occurrences of any value is within some bounds [Schaus et al., 2007]; that two overlapping sets of variables both have all pairwise distinct values [Kutz et al., 2008]; that there is an upper bound on the cardinality of the set of assigned values [Bessiere et al., 2006a]; that a sequence of variables encode the successors of an Hamiltonian circuit of bounded length in a graph [Ducomman et al., 2016]; or that a set of tasks share a disjunctive [Baptiste and Le Pape, 1995] or cumulative resource [Baptiste and Le Pape, 1997].

However, whereas one can enforce domain consistency on polynomial constraints, it is often necessary to find a compromise between inference strength and computational effort on NP-complete constraints. In this paper, we advocate the design of propagation algorithms for NP-complete constraints. Furthermore, we argue that there is a need for a theoretical characterization of the consistency enforced by these algorithms. We show that fixed-parameter tractability [Downey et al., 1999], and in particular the notion of kernel are extremely relevant in this context and that the latter can be extended to fill this role of measure of propagation strength.

2 NP-complete Constraints

A constraint network is a triple (X, U, C) where X is a totally ordered set of variables, the universe U is a finite set of values and C is a set of constraints. A constraint C is a pair (SC,RC) where the scope SC is a subset of X and RC is a relation on U of arity |SC|. The Constraint Satisfaction Problem (CSP) asks whether a constraint network (X, U, C) has a solution, that is, a |X|-tuple σ ∈ U |X| such that for each C ∈ C, the projection σ(SC) of σ onto SC is in RC.

A global constraint is a class of relations, one for each possible value of its parameters. The most common parameter is the number of constrained variables. For instance we can define the NVALUE [Pachet and Roy, 1999] constraint with one relation per integer n given by the following predicate:

Definition 1 (NVALUE).

During search, in order to store the decisions and deductions, we use a special type of relation over X , the domain D. There is not a unique type of relation used for that purpose, for instance the search space can be encoded as a Boolean Decision Diagram [Hadzic and Hooker, 2007]. However we consider here the canonical finite discrete domain where the D relation is restricted to conjunctions of finite unary relations, one for every variable x ∈ X , which we denote D(x). We write D′ ⊆ D as a shortcut for ∀x ∈ X D′ (x) ⊆ D(x).

Definition 2. A constraint C is said domain consistent on a finite discrete domain D if and only if

The problem of achieving domain consistency of a domain D with respect to a constraint C consists in finding the largest domain D′ ⊆ D such that C is arc consistent on D′ . There is a unique largest arc consistent closure of a finite discrete domain D with respect to a constraint C.

Notice that achieving domain consistency is polynomially reducible to checking the satisfiability of a constraint, i.e., finding a tuple τ ∈ D ∩ C. Given an algorithm for checking satisfiability, for every variable x and every value v ∈ D(x) one can check the satisfiability of C w.r.t. D′ where D′ (x) = {v} and D′ = D otherwise. If the constraint is not satisfiable, then the domain consistent closure of D is such that v ̸∈ D(x) and we can change D accordingly. Otherwise the domain consistent closure is such that v ∈ D(x) and we leave D unchanged. This procedure terminates after ∑x∈SC |D(x)| steps. The converse is trivial, since a constraint is satisfiable if and only if its domain consistent closure is not empty. We therefore say that a constraint is NP-complete if checking its satisfiability is NP-complete, even though achieving domain consistency is not a decision problem.

The constraint NVALUE is NP-complete since checking if there exists a tuple in a domain D such that |{τ(xi) | 1 ≤ i ≤ n}| ≤ y is equivalent to finding a hitting set of the collection {D(x1), . . . ,D(xn)} of size maxD(y) [Bessiere et al., 2006a]. Therefore, achieving the domain consistent closure is often considered too costly for this constraint. For NVALUE and other NP-complete constraints incomplete approaches are used instead.

Relaxing the domain: A common way to reduce the complexity of propagating a constraint is to relax the domain relation D. For instance, the notion of bounds consistency is widely used in this situation. Let interval domains be the class of relations restricted to conjunctions of finite unary relations, one for every variable x ∈ X , of the form l ≤ x ≤ u. Bounds consistency is the property obtained by applying Definition 2 to interval, instead of discrete, domains.

The hitting set problem has a polynomial algorithm when the sets are discrete intervals. Therefore, the relaxtion from finite discrete domains to interval domains make satisfiability checking and thus bounds consistency polynomial. The best algorithm achieves both in O(|X| log |X|) [Beldiceanu, 2001]. This is true for many NP-complete global constraints. For instance the constraint GCC, which channels the number of occurrences of values in a set of variables X to another set of variables Y is NP-complete for discrete domains [Quimper et al., 2004], but polynomial if the domain relation is relaxed to intervals for the variables Y [R´egin, 1996].

Decomposing the constraint: Another common way to deal with NP-completeness is to decompose the constraint. A constraint network I = (X,D, C) is a decomposition of a constraint C if and only if SC ⊆ X and σ is a solution of I if and only if σ(SC) ∈ RC. In other words, it is a constraint network on a superset of SC such that its set of solutions, when projected onto SC is exactly the set of tuples in RC.

Decompositions are used in countless constraint programming approaches. A lot of effort has been put into the study of decompositions and in particular when it is or when it is not possible to emulate algorithms through decompositions, both for polynomial and NP-complete constraints [Narodytska, 2011]. For instance, it was shown that propagation algorithms for the NVALUE constraint can be emulated for the same time complexity, however at the cost of a much higher space complexity [Bessiere et al., 2010].

Moreover, decompositions are sometimes used as a way to relax the problem of achieving the domain consistent closure, even though an efficient dedicated algorithm is then proposed to compute the closure. For instance the O(n logn) "Timetabling" method for reasoning about a set of n tasks consumming energy from a cumulative resource [Le Pape, 1988; Beldiceanu and Carlsson, 2001] over time can be seen as achieving bounds consistency on a decomposition involving Boolean variables xij standing for whether task i is processed at time j, however with a far lower time complexity. Similarly, "Edge Finding" algorithms [Nuijten and Aarts, 1994; Vil´ım, 2009] achieve bounds consistency (in polynomial time) on a decomposition (of exponential size). Lastly, Ouellet and Quimper's algorithm [Ouellet and Quimper, 2013] achieves bounds consistency on the conjunction of these two decompositions in O(kn logn) time with k the number of different tasks' consumptions.

Approximation: Often, NP-complete constraints on a set of variables X can be easily seen as enforcing that an |X|-ary cost function π : D|X| ↦→ Q ∪ {∞,-∞} is non-positive. 2 For instance, the constraint NVALUE corresponds to the following cost function: |{xi | 1 ≤ i ≤ n}|-y. The intersection graph of {D(x1), . . . , D(xn)} is the graph with one vertex vi for i ∈ [1, n] and an edge (vi, vj) iff D(xi)∩D(xj) ̸= ∅. The independence number of this graph is larger than or equal to the minimum hitting set of the collection. Therefore, this is a valid upper lower bound for y [Bessiere et al., 2006a]. In this case, the approximation offers no guarantee, yet it is a relatively effective method in practice, often outperforming the bounds consistency approach.

2 This is not restrictive as any relation maps tuples to 0/1.

More generally, when a method with a guaranteed approximation ratio exists for a cost function π, this method provides both a primal and a dual bound which is extremely valuable. In general, however, approximation results are still largely underused within the context of constraint propagation.

3 Propagation via Kernels

The complexity of a problem can be more finely characterized by considering parameters besides the size of the input. Parameterized complexity aims at understanding which parameters are relevant to explain the hardness of a problem. Given a problem P and a parameter p, (P, p) is in the FPT class if there exists an algorithm that can decide an instance I of P in time f(p)|I|O(1) where f is a computable function.

A previous study [Bessiere et al., 2008] of the parameterized complexity of global constraints, and of their relevant parameters, showed that this approach was promising. In particular, the NVALUE constraint is FPT when the parameter is the number of "holes" in the domains [Bessiere et al., 2008].

Moreover, it is often possible to compute kernels of FPT problems, which are extremely relevant in this context.

Definition 3. A kernelization for a problem P and a parameter p is a polynomial-time computable function that maps each instance x and parameter value k to an instance x′ and parameter k′ of the same problem such that x is a yesinstance if and only x′ is, |x′ | ≤ f(k), and k′ ≤ g(k) for some computable functions f, g.

There is intense research both on FPT algorithms and kernelization methods [Cygan et al., 2015]. Characterizing a kernel is a very significant step in understanding the combinatorial structure and efficiently reasoning about a constraint. Intuitively, the difference between the original instance and the kernel is composed of inconsistent (or entailed) values.

Consider for instance the vertex cover problem, asking whether there is a subset of at most k vertices of a graph G, such that every edge has at least one extremity in the cover. The Buss rule consists in adding vertices of degree k+1 to the cover, since otherwise their neighbors would be in the cover. This very simple propagation rule yields a kernel of size k2 .

However, classical kernels are not always correct propagation. For instance, the smallest kernels for the vertex cover problem [Abu-Khzam et al., 2007; Nemhauser and Trotter Jr, 1975] are based on crown decompositions of the graph.

Definition 4. A crown decomposition of a graph G is a partition (H,W, I) of V such that vertices in I have an edge only with vertices in W and there is a matching of size |W| between W and I.

The size of a vertex cover can never be increased by removing all vertices from I and adding all vertices from W. However, this is a correct dominance rule, but not a correct propagation rule: feasible or even minimal solutions might involve vertices from I. Similarly, an efficient kernelization using dominance was proposed for the NVALUE constraint [Gaspers and Szeider, 2011]. For the same reason, this method is to be used within the probing procedure described in Section 2 to achieve domain consistency through satisfiability checks: for every variable-value pair, the problem of deciding if the constraint is satisfiable when restricting the domain accordingly is solved on the kernel. In other words, several exponential satisfiability checks have to be performed.

In [Carbonnel and Hebrard, 2016; 2017] we proposed an approach to propagating NP-complete constraints based on a new definition of "loss-less" kernelization tailored for constraint propagation. Intuitively, z-loss-less kernels are kernels with an extra loss-lessness property: Whereas solving a classical kernel is sufficient to solve the original instance, achieving domain consistency on a loss-less kernel is sufficient to achieve domain consistency on the original instance. In other words, there exists a polynomial algorithm, which, given the domain consistent closure of the loss-less kernel, computes it for the original instance. This is much more consistent with the spirit of kernelization, extends smoothly constraints with polynomial-time propagators and yields a propagation algorithm with running time O(g(p) + |I|O(1) pO(1) ), instead of O(|I|O(1) g(p)) for probing plus classical kernelization.

There is caveat, however. Consider again constraints defined as minimizing a cost function, for instance the NVALUE constraint which ensures that the cardinality of the set of values taken by the variables x1, . . . , xn is at most y. As long as the domain of y contains high values, the constraint is unlikely to propagate much. In fact, if n ∈ D(y) then the constraint is completely inoperant. More generally, kernels whose size decrease when the constraint get tighter should be priotirized since they are the most useful with respect to propagation. When defining constraints as minimizing a cost function such as the NVALUE constraint, the tightness is very clearly related to the gap z from 0 to the minimum of πD(X) under the current domain D. We therefore use this extra parameter z in the definition of loss-less kernels:

Definition 5. Let Π be a set of cost functions, and C a global constraint defined as the relations π(X) ≤ 0 for π ∈ Π.

A z-loss-less kernelization of C with parameter p is a polynomial-time computable function mapping each instance (π,X,D) and parameter value k to an instance (π′ ,X ′ ,D′ ) and parameter k′ of the same constraint such that if -min(πD(X)) ≤ z, then there is a polynomial algorithm achieving domain consistenty of D w.r.t. π(X) ≤ 0 given the the domain consistent closure of D′ w.r.t. π′ (X ′ ) ≤ 0, |π′ | + |D′ | + |X ′ | ≤ f(k), and k′ ≤ g(k) for some computable functions f, g.

The results in [Carbonnel and Hebrard, 2017] show that loss-less kernels exist: There is a (z + 2)k z-loss-less kernel for the vertex cover problem parameterized by the size k of the cover, thus matching the result of Nemhauser [Nemhauser and Trotter Jr, 1975] for z = 0.Similarly, there is a ∞-lossless kernel max(6k, k2 /2 + 7k/2) kernel for the edge dominating set parameterized by the size of the dominating set, thus matching the result of Hagerup [Hagerup, 2012].

Moreover, they are not mere theoretical curiosities: kernelbased propagation was successfully applied to a constrained vertex cover problem [Carbonnel and Hebrard, 2016].

4 Conclusions

In this paper we have surveyed different approaches to propagating NP-complete constraints and argued that designing dedicated methods is extremely valuable. Moreover, among the possible ways of tackling the propagation of NP-complete constraints (approximation, relaxation, decomposition, etc.) we argue that fixed parameterized complexity and in particular kernelization offers several extremely relevant features:

Firstly, the value of the parameter, as well as the size of the gap z, changes during search. Therefore, it is possible to target when kernelization is most likely to being beneficial and thus use it in an opportunistic way.

Secondly, loss-less kernels are designed to achieve domain consistency of the full instance with a single call to a possibly exponential algorithm to compute the closure of the kernel. However, in practice, the kernelization procedure in itself makes some incomplete inference while being polynomial. The kernelization process in itself can therefore be used as a polynomial propagation procedure.

Finally, the guarantee on the size of the kernels entails a guarantee on the strength of this inference. In other words, the size of the kernel is a valuable criterion to compare the achieved level of consistency.