Computational Complexity of Multi-way, Dataflow Constraint Problems

1 Introduction

Dataflow constraints are rapidly gaining popularity in interactive applications because they simplify the pro­ gramming task. They are conceptually simple and easy to understand, and are capable of expressing re­ lationships over multiple data types, including num­ bers, strings, booleans, bitmaps, fonts, and colors [Van­ der Zanden, 1996]. Dataflow constraint solvers are used in numerous interactive systems, such as graphical user interfaces, spreadsheets, graphical layout systems and animation.

Dataflow constraints are divided into two main cate­ gories. A one way dataflow constraint has one associated function for recovering its consistency. This function cal­ culates output variables using the current value of input variables. The spreadsheet model, more formally known as the dependency graph model [Hoover, 1987], only takes into account one-way constraints. This model is widely used in interactive systems, mainly because the solving process is based on an efficient incremental evaluation phase that topologically sorts the functions to execute.

A multi-way dataflow constraint has several functions (called methods) that may be used to satisfy it. The solving process of problems that contain. multi-way con­ straints needs an additional planning phase that assigns a method to each constraint, before the evaluation phase.

Although multi-way constraints are more expressive than one-way constraints, they are less recognized be­ cause of concerns about their tractability. Every solving algorithm handles a specific problem and the conditions that allow us to decide whether it is computationally difficult are not clear by now.

This paper aims at giving a classification for the com­ putational complexity · of the main existing multi-way constraint problems.

2 Background

A multi-way dataflow constraint system can be denoted as (V, C, M). Vis a set of variables with a current value. C is a set of dataflow constraints and M is a set of meth­ ods that can satisfy the constraints.

Definition 1 A multi-way dataflow constraint is an equation that has one or more methods associated that may be used to satisfy the equation.

A method consists of zero or more inputs, one or more outputs, and an arbitrary piece of code that com­ putes the output variables based on the current value of the input variables [Vander Zanden, 1996]. A single­ output method determines only one variable.

A (dataflow) constraint system is often represented by a constraint graph Gc as shown in Figure 1 (a).

Local propagation is the technique used to solve multi­ way constraint systems, typically when new constraints are incrementally added. It works in two phases:

• The planning phase directs the edges in G c by as­ signing one method to each constraint. The result of this phase (i.e., the solution of the corresponding problem) is a valid graph Gm called method graph (see Figure 1 (b) and (c)).

Definition 2 A method graph Gm is valid if {1) every constraint has one method associated with it in Gm, and {2) Gm has no variable conflicts, that is, each variable is the output of, at most, one method (i.e., has at most one incoming edge).

• When the method graph Gm contains no directed cycles, the evaluation phase executes the methods in some topological order. When a method is executed, it sets the output variables to values such that the constraint is satisfied. When Gm is cyclic, strongly connected components are collected and generally passed to external solvers to be satisfied as a whole.

Ignoring the operations involved in method execution and cycle solving, the evaluation problem is in the class P of polynomial problems. Indeed, topological sort is O(d x ICI) where dis the maximum number of methods associated to one constraint. We concern ourselves with the computational complexity of the problem solved by the planning phase that will be called constraint plan­ ning problem in the following.

Planning algorithms can be divided into three main categories. (1) DeltaBlue [Freeman-Benson et al., 1990] and SkyBlue [Sannella, 1994] work by propagating the conflicts from the perturbations to the leaves of the con­ straint graph. (2) The propagation of the degrees of freedom scheme (in short PDOF) selects the methods in the reverse order (i.e., executing first the methods that were chosen last). This algorithm has been used in SketchPad [Sutherland, 1963] and QuickPlan [Van­ der Zanden, 1996]. (3) A third approach is related to the classical problem of graph matching. It gives the Maximum-matching algorithm [Gangnet and Rosenberg, 1992].

3 Different types of constraint planning problems

Existing local propagation algorithms solve different planning problems that imply various tradeoffs between expressiveness and performance:

• required constraints only, or both required and preferential constraints that are satisfied if possible
• single-output constraints only, or multi-output ones
• acyclic constraint graphs only, or cycles allowed
• method restriction imposed or relaxed

Definition 3 The method restriction imposes that every constraint method of a given problem must use all of the variables in the constraint either as an input or an output variable {Vander Zanden, 1996].

Moreover, some systems allow directed cycles in the method graph, whereas others do not, which le9-ds in fact to two different (and incomparable) problems. Indeed, a general computational result states that a restriction imposed on a solution does not necessarily make the cor­ responding problem easier [Papadimitriou, 1994].

Table 1 shows the computational complexity of se­ lected existing constraint planning problems.

4 An NP-complete planning problem with method restriction

Disjunctive constraints do not respect the method re­ striction (e.g., constraint a V b has two methods that out­ put to either variable a or b with no input). However, these constraints are not usually needed in interactive systems. Therefore, all of the propagation algorithms impose the method restriction. The problems handled by these algorithms are in P, except cp2 (see Table 1) which has not been yet analyzed.

The only known NP-completeness results aim at prob­ lems acp3 and acp4 [Maloney, 1991] which are not very interesting in practice because they relax the method restriction.

The following theorem states an NP-completeness re­ sult about the problem cp2 for which the method restric­ tion holds and which is handled by SkyBlue.

Theorem 1 Let G be a dataflow constraint system for which the method restriction holds.

Then proving the existence of a valid method graph (cyclic or not) corresponding to G is NP-complete.

The proof and the polynomial reduction involved in it are described in following paragraphs.

4.1 Polynomial reduction

In Section 4.2, we prove that the known NP-complete problem "Exact Cover by 3-Set!l' [Papadimitriou, 1994]

can be reduced to "constraint-planning' (i.e., cp2). This reduction will be called planning reduction.

Definition 4 (Exact Cover by 3-Sets) Let X be a finite set, such that lXI = 3q for some integer q. Let E be a family of sets that contain 3 elements of X each. Every element of X belongs to at least one 3-set of E . 1

Does E contain an exact cover for X, that is, a subset S of E such that every element of X belongs to exactly one 3-set of S?

Let G = (X, E) be an instance of "Exact Cover by 3Set~'. Let G' = (V, C, M) be an instance of" constraint­ planning' obtained by a planning reduction applied to G as follows:

• Variables in V are divided into two sets VarX and VarE. Constraints in C are divided into two sets ConstX and ConstE.
• Each element i of X corresponds to one variable i-at-most of Var X.

1 This additional hypothesis discards trivial instances while keeping the problem NP-complete.

• A 3-set p = {a, b, c} in E corresponds to a constraint setp of ConstE connecting six variables. setp has two triple output methods which indicate whether the 3-set p is either present or absent in the solution. The present method outputs to the three variables a-at-most, b-at-most, c-at-most of Var X (It ensures that no other 3-set will cover the corresponding el­ ements.) The absent method outputs to the three variables a-p, b-p, and c-p of VarE.
• When element i of X can be covered by n differ­ ent 3-sets {Pl ···Pn} of E, n variables {i-Pl···i-pn} of VarE are constructed. One constraint i-at-least of ConstX is also built, that connects these variables. i-at-least has n single-output methods, one for each variable in the constraint. The method that out­ puts to variable i-pk ensures that element i of X is covered by (at least) the 3-set Pk.

Figure 2 shows an instance of" Exact Cover by 3-Set~' that is reduced to the "constraint-planning' instance of Figure 3.

The planning reduction is based on the following in­ tuition. One element i of X appears in exactly one 3-set of solution S. Thus, i appears at most once and at least once in a 3-set of S. This is translated into the planning problem as follows:

• (at most once) If the 3-set p belongs to solution S, then the present method of setp is selected in the corresponding constraint planning problem. Thus, the variables determined by setp ensure that no other 3-set than setp covers them, as this would lead to variable conflicts.
• (at least once) As said above, a constraint i-at-least directed onto variable i-p ensures that element i of X is covered by the 3-set p in the solution. In fact, no method can be selected for constraint i-at-least (thus involving no solution) if every connected vari­ able is the output of an absent method.

4.2 Proof of Theorem 1

First, the planning reduction is O(JXJ +JEI). Indeed, one 3-set of E corresponds to one constraint, five methods, nine edges, and three variables in the planning problem. One element of X corresponds to one constraint and one variable.

Second, "constraint-planning' is in NP since verifying that a method graph issued from a planning reduction is valid is O(JVJ+JCI). Indeed, it just has to be verified that every variable is determined by at most one constraint, and that every constraint has one method selected for it.

Finally, the two following paragraphs prove the equiv­ alence between (i) a solution S for any instance G of "Exact Cover by 3-Sets' and (ii) a solutionS' for the in­ stance G' of" constraint-planning' obtained by applying to G the planning reduction.

(i) -+ (ii) Based on S, S' is obtained by selecting present methods for the constraints setp in ConstE when the 3-set p is in S. The absent method is selected for the 3-sets that are not in S. Every constraint i-at-least in ConstX is directed onto variable i-p of VarE when the 3-set p is in S . Variable i-p is an input of the present method selected for the constraint setp in ConstE. By construction, every constraint has one method selected for it. ·

By hypothesis, every element of X belongs to exactly one 3-set of S. Since there is no intersection between any two 3-sets in S, this construction does not generate conflicts on variables i-at-most of Var X.

Every element i of X is covered by (at least) one 3set p of S. By construction, setp is activated with the present method that outputs to i-at-most. By construc­ tion, variable i-p is determined by constraint i-at-least, thus there is no variable conflict generated on i-p. The other variables of constraint i-at-least do not provide con­ flicts because they are linked only to two constraints and are not determined by i-at-least. Thus, for every element i of X, no corresponding variable in the constraint plan­ ning problem can cause a variable conflict.

( ii) -+ ( i) Based on S', S is built by collecting a 3set {a, b, c} when the present method that outputs to variables a-at-most, b-at-most, and c-at-most is selected. Since the method graph is valid, the intersection of any two 3-sets in S is empty.

Let us consider every constraint i-at-least of ConstX in S'. Let i-p be the variable determined by i-at-least. i-p is necessarily an input variable of constraint setp that determines variable i-at-most, otherwise a variable con­ flict would occur on i-p. By construction, i necessarily belongs to a 3-set in S. D

4.3 Complexity of 2-output constraint planning problems

We know that when" constraint-planning' is restricted to single-output constraints, the problem complexity comes down to P (cp1). The planning reduction shows that "constraint-planning' is NP-complete with 3-output constraints. A natural question is therefore, whether the 2-output constraint restriction would yield a polynomial problem or not.

Theorem 2 Let G be a dataflow constraint system for which the method restriction holds. G contains methods that have at most two outputs.

Then proving the existence of a valid method graph (cyclic or not) corresponding to G is NP-complete.

Proof. Every 3-output constraint setp can easily be transformed into two 2-output constraints and a

"dummy" variable, as shown in Figure 4. The global behavior remains exactly the same 2 . 0

5 Influence of the method restriction on problems with cyclic solutions

The following theorem states that the method restriction has no influence on the computational complexity of the constraint planning problem when cyclic solutions are allowed.

Theorem 3 Let C be a class of dataflow constraint sys­ tems and let Pc be the problem of existence of a valid method graph (cyclic or not) for any instance in the class C. Let Pb be the restriction of Pc to constraint systems that satisfy the method restriction.

Then Pc and Pb are polynomially (actually LOG­ space) equivalent.

The proof is based on the method transformation.

Definition 5 Let G1 = (V1 , C1, M1) be a constraint sys­ tem. Based on G1, the method transformation provides a constraint system G2 = (V2 , C2 , M2 ) such that: (1) V1 = V2, (2) C1 = C2, (3) methods in M1 for which the method restriction holds, occur unchanged in M2, and (4) every method m1 in M1 for which the method re­ striction does not hold is replaced by a method m2 in M2 for which the method restriction holds: m2 has the same output variables as m1 and has all of the other variables of the associated constraint as input.

Note that this trivial transformation is LOG-space. Thus, Theorem 3 can be applied to problems that are in P or are NP-complete.

Proof of Theorem 3. First, Pb can be reduced to Pc since Pb is a restriction of Pc. Second, Pc can be reduced to Pb thanks to the method transformation that reduces a constraint system G1 into a constraint system G2 for which the method restriction holds. We prove the equivalence between (i) a solution of G1 and (ii) a solution of G2 .

2 Figure 3 illustrates that every variable is determined by a constraint. Thus, no solution can be found for 2-output constraint problems when the two 2-output constraints are selected in opposite directions.

(ii) ---+ (i) A valid method graph of G2 can be trans­ formed into a valid method graph of G1 since G1 is the same as G2 without certain edges. This does not induce variable conflicts.

(i) ---+ (ii) A valid method graph of G1 can be trans­ formed into a valid method graph of G2 since every edge added by the method transformation connects a con­ straint and one of its input variable. This does not gen­ erate variable conflicts. 0

Note that if directed cycles are not allowed in the so­ lution, the last implication is false because adding an input edge could introduce a directed cycle.

6 Synthesis

These three theorems allow us to deduce the three miss­ ing computational complexity results, as shown in Ta­ ble 2. Since cp2 (which is NP-complete) is a restriction of cp4, and cp4 is in NP, cp4 is also NP -complete 3 . The­ orem 3 proves that cp1 and cp3 have the same computa­ tional complexity.

Since the table is now complete, we can highlight in­ teresting points about the constraint planning problems handled by existing algorithms.

SkyBlue Problem cp2 assumes that the constraints must be required, whereas SkyBlue [Sannella, 1994] can handle one type of preferential constraints. Therefore, the SkyBlue problem is NP-hard. The NP-completeness result given by Theorem 1 makes the exponential worst case time complexity of SkyBlue less surprising. How­ ever, [Sannella, 1994] has proven that SkyBlue could reach this worst case complexity even on problems aCP2 and cp1 that are in P.

QuickPlan QuickPlan [Vander Zanden, 1996] cannot be extended without making the corresponding problem NP-complete. Indeed, the gap between acp2 (in P) and acp4 (NP-complete) is due to the method restriction, as described in [Vander Zanden, 1996]. Moreover, the gap between acp2 (in P) and cp2 (NP-complete) is due also to cyclic solutions being accepted or not.

3 Theorem 3 applied to cp2 and cp4 also proves this result.

The companion paper [Trombettoni and Neveu, 1997] proves that there exist instances of"constraint-planning' issued from the planning reduction which only have cyclic solutions (otherwise P would be equal to NP).

Maximum-matching The Maximum-matching prob­ lem is in P [Gangnet and Rosenberg, 1992]. Since the gap between cp1 and cp2 lies in the single-output con­ straint restriction, Maximum-matching cannot be ex­ tended to multi-output constraints.

Note that Maximum-matching can also solve problem cp3. Indeed, Theorem 3 can easily be extended to the problem of finding a solution, thanks to a reverse trans­ formation. So one needs to (1) transform an instance of cp3 into one of cp1 with the method transformation, (2) call Maximum-matching on the cp1 instance and (3) retrieve the solution (if any) with the reverse method transformation.

7 Complexity of problems with acyclic constraint graphs

We know that an acyclic constraint graph cannot yield a method graph with directed cycles. The restriction of the two problems acpi and cpi ( i E { 1. .4}) to acyclic constraints graphs is then a unique problem p~. ·

Problems p~ and p~ are in P because they are restric­ tions of acp1 and acp2. In the same way, p~ is in P since it is a restriction of cp3. p~ and p~ can be seen as problems where cyclic solutions are allowed (in fact, all solutions are acyclic and one does not need to disallow cyclic solutions). They satisfy the conditions of Theo­ rem 3 so that p~ is in P. We can then conclude that all of the restrictions to acyclic constraint graphs are in P.

8 Conclusion

We have proven new computational complexity theo­ rems. First, the constraint planning problem handled by SkyBlue is NP-hard. We do not know yet whether it is in NP, when handling constraint hierarchies that are a widely used type of preferential constraints. Second, the computational complexity is insensitive to the method restriction when cyclic solutions are allowed. Based on the theoretical results presented in this paper, the follow­ ing simple rule gives sufficient conditions to determine if a given constraint planning problem is in P.

if the constraint graph contains no cycle then the problem is in P

else if an acyclic solution is expected then

the problem is in P if the method restriction is imposed else

the problem is in P if it only contains single-output constraints This rule highlights the importance of the "cyclic/ ­ acyclic solution" condition. When directed cycles are not allowed in the solution, the gap between problems in P and NP-complete problems comes from the method restriction, and not from the single-output constraint re­ striction. The problem complexity has exactly the op­ posite behavior when cyclic solutions are allowed. Fi­ nally, the companion paper shows that the polynomial complexity of problem acp1, acp2, cp1, or cp3 is not lost when handling constraint hierarchies.

We believe that these results will help designers to con­ ceive multi-way constraint systems that provide a good balance between expressiveness and performance.

Acknowledgements

Special thanks to N. Chleq and T . Schiex whose com­ ments were very helpful. Also thanks to C. Bliek, C. Lottaz, N. Prcovic, and R. Stalker.