On the Space-Time Trade-off in Solving Constraint Satisfaction Problems

1 Introduction

The constraint satisfaction problem (CSP) is a combinatorial search problem whose occurrence in AI and other domains is well documented. Briefly, a CSP consists of a set of vari­ ables to which values must be assigned without violating constraints that disallow certain value combinations. In the general case, the CSP is NP-hard, and worst-case runtime of a CSP algorithm is typically exponential in the number of variables. Improved bounds are achieved on some problems by algorithms that exploit problem specific features . A com­ mon technique is to exploit the structure of the problem's constraint graph [Dechter, 92]. The constraint graph of a CSP graphically depicts constraint relationships by repre­ senting each variable with a vertex and each constraint with edges connecting the restricted set of variables. In general, the more sparse the constraint graph, the tighter the bound on runtime. For instance, problems with noncyclic constraint graphs can be solved in time linear in the size of the problem [Dechter & Pearl, 87; Bayardo & Miranker, 94].

* This research was partially supported by an AT&T Bell Labora­ tories Ph.D. fellowship.

2 Constraint Satisfaction Problems and Backtracking

A constraint satisfaction problem (CSP) is a set of variables and a set of constraints. Each variable is associated with a finite value domain, and each constraint consists of a subset of the problem variables called its scheme and a set of map­ pings of domain values to variables in the scheme. An assignment is a mapping of values to a subset of the problem variables where any value mapped to a particular variable belongs to the domain of the variable. An assignment A sat­ isfies a constraint C with scheme X if A restricted to the variables in X is a mapping in C . A partial solution to a CSP is an assignment that satisfies every constraint whose scheme consists entirely of variables mentioned in the assignment. A solution to a CSP is a partial solution men­ tioning every variable.

The constraint graph of a CSP has a vertex for each variable and the property that the variables in the scheme of a constraint are completely connected. This is referred to as the primal-constraint graph in [Dechter, 92] when there are constraints with more than two variables in their schemes. Without loss of generality, we assume problems have con­ nected constraint graphs. If it were otherwise, we could sim­ ply view the disconnected instance as a set of instances, one for each connected component.

A naive method for solving constraint satisfaction problems is chronological backtrack. Chronological back­ track maps values to variables along an ordering of the vari­ ables until some constraint is violated by the working assignment. When a constraint is violated, the variable most recently to have been assigned a value is assigned another value from its domain. If ever the values in the domain of a variable are exhausted, a backtrack takes place to the previ­ ous variable along the ordering. The procedure continues until either the last variable is successfully assigned a value (in which case a solution has been found), or until all values from the domain of the initial variable are exhausted (in which case no solution exists). If we let k bound the number of values in any domain and n denote the number of vari­ ables, then chronological backtrack has a runtime complex­ ity of O(exp(n)) because a variable can be assigned a value up to kn times.

3 Pseudo-tree Arrangements and Pseudo-tree Search ·

Freuder and Quinn [ 1985] introduce the concept of a pseudo­ tree arrangement of a graph. A pseudo-tree arrangement of a graph is a rooted tree with the same set of vertices as the original graph and the property that adjacent vertices from the original graph must reside in the same branch of the rooted tree (hereafter called the pseudo tree). A branch is simply a path from the root to some leaf. The concept is illustrated in Figure 1, where a vertex in the rooted tree cor­ responds to the vertex directly above it in the original graph.

The original edges from the graph appear dashed in the pseudo tree to illustrate that adjacent vertices always appear within the same branch. Note that while a depth-first search tree is a pseudo tree, a pseudo-tree is not necessarily a depth­ first search tree. For instance, the pseudo tree appearing in the figure is not a depth-first search tree.

Pseudo-tree search [Freuder & Quinn, 85] exploits pseudo-tree arrangements, and has a worst-case complexity function that is exponential in the height of the pseudo tree ( h ). Rather than explain pseudo-tree search in its full detail, we instead describe how to modify chronological backtrack so that it exploits pseudo trees in a similar fashion. Given a pseudo-tree arrangement of the problem's constraint graph, we order the variables of the problem according to a depth­ first traversal of the pseudo tree. 1 Now, whenever a back­ track is necessary, instead of backing up to the previous vari­ able in the ordering, we backtrack to the pseudo-tree parent of the current variable, possibly skipping over many vari­ ables in the process. This backtrack policy does not sacrifice completeness because, due to the structure of the pseudo tree, the assignments made to the skipped variables are irrel­ evant with respect to the current failure. We call this algo­ rithm pseudo-tree backtrack.

Given the pseudo-tree arrangement, pseudo-tree backtrack has runtime complexity O(exp(h)) since each variable can be assigned a value a maximum of kh times. The space requirement of this technique is a mere O(n) beyond the size of the problem input to maintain domain value iterators and the variable ordering.

In order for pseudo-tree backtrack to be effective at bounding runtime, it requires a pseudo-tree arrangement with shallow height. An efficient algorithm for finding the minimum-height pseudo-tree is not known. Though a proof eludes us, we suspect the problem is NP-hard due to its simi­ larity to various well-known NP-hard problems including minimizing depth-first search tree height.

1 Note that the variable ordering need not be static since there are typically many different depth-first orderings. Dynamic variable ordering involves modifying the unassigned portion of the ordering during backtrack, and can improve average-case per­ formance [Haralick & Elliot, 80; Frost & Dechter, 94].

Freuder and Quinn [1985] provide the following method for heuristically constructing a pseudo-tree arrange­ ment: Find a small set of vertices S whose removal from the constraint graph disconnects it (such a set is called a cutset). These vertices will form the first lSI levels of the tree. The remaining levels are formed by recursively applying the pro­ cedure to the remaining graph components in order to spawn branches (one for each component) beginning at level lSI + 1 . It is easy to verify that the resulting structure is indeed a pseudo-tree arrangement. The pseudo-tree from Figure 1 can be constructed in this manner by selecting the middle vertex in each chain at each step to disconnect the remaining graph.

Depth-first search can also be regarded as a heuris­ tic technique for pseudo-tree arranging a graph. Although, we have found it unlikely to find an arrangement with small height even when additional heuristics are applied. For example, consider an n vertex chain graph. Any depth-first search tree has height at least ~ , whereas a pseudo-tree arrangement always exists with lleight at most lg(n) + 1 (e.g. as implied by Figure 1).

4 Induced Width

Dechter [ 1992] demonstrates that the best structure-based algorithms for solving the CSP are exponential--in both time and space--in a constraint graph parameter called induced width (w* ). The actual exponent in the complexity function of these schemes, e.g. adaptive consistency [Dechter, 92], is w * + 1 . The parameter is obtained from the constraint graph after imposing a variable ordering on which the algorithm operates. A child of a vertex in a graph with an ordering of its vertices (an ordered graph) is an adjacent vertex that fol­ lows it in the ordering. A parent is an adjacent vertex that precedes it. The induced graph of an ordered graph G is an ordered graph with the same ordered set of vertices as G and the smallest set of edges to contain the edges of G and enforce the property that any two vertices sharing a child are adjacent. We can build the induced graph of G by iteratively connecting any nonadjacent vertices that share a child. Finally, the induced width of an ordered graph G is the max­ imum number of parents of any vertex in the induced graph of G .

Figure 2 illustrates the process of creating the induced graph. The ordering is assumed to be from top to bottom. Edges added to form the induced graph are dashed. Note that the graph has an induced width of 3.

Like schemes exploiting pseudo trees, the effective­ ness of techniques exponential in induced width depends upon the quality of the constraint graph arrangement. Mini­ mizing induced width is NP-hard [Arnborg, 85], so heuristic techniques are typically applied to produce the ordering.

We can always order a graph so that its induced width is less than the height of any pseudo-tree arrangement. Given a pseudo-tree arrangement of a graph G with height h , ordering the vertices of G according to a depth-first tra­ versal of the pseudo tree produces an ordered graph with induced width w* :5: h- 1 . This is because when creating the induced graph from such an ordering, no edge can be added between vertices in different branches of the pseudo tree. The number of parents of any vertex in the induced graph is thus bounded by the number of its pseudo-tree ancestors.

The above establishes that techniques exponential in induced width can always be made as effective in bound­ ing runtime as techniques exploiting pseudo trees. In fact, for certain classes of problems, induced width is usually better. For instance, any noncyclic graph can be ordered to have an induced width of 1, but pseudo-tree arrangements of chain graphs must increase at least logarithmically with the num­ ber of vertices.

In the next section, we bound how much more effective induced width techniques are in the general case. Before proceeding, we review a useful fact relating induced width to k-trees. A graph is a k-tree [Beineke & Pippert, 71] if:

• the graph has k vertices and is complete (said to be a trivial k-tree), or
• there is a vertex of degree k whose neighborhood induces a complete graph, and the graph obtained by removing the vertex is a k -tree.

Note that a connected noncyclic graph is a 1-tree. A partial k-tree is a partial graph of a k-tree. The following is due to Freuder [ 1990]:

THEOREM 4.1: An ordered graph with induced width w * is a partial w * -tree.

5 Relating Pseudo-Tree Height and Induced Width

We now show that given an ordered graph, we can construct a pseudo-tree arrangement of the graph where h is within a logarithmic factor of w * . This implies that no matter how effective we can make induced width techniques solve par­ ticular classes of problems, we can make pseudo-tree search solve them almost as effectively without the added burden of an exponential space requirement.

The idea behind our approach is to generalize the case for 1-trees to that of general graphs by making use of k­ tree embeddings.lt is easy to establish that a 1-tree of n ver­ tices can be split into components that contain at most ~ vertices by removing a single vertex. We can therefore gen­ erate a pseudo-tree arrangement with h s; lg(n) + 1 of any 1tree using the heuristic arrangement method from Section 3. The idea is to always select for the cutset a vertex whose removal splits the remaining graph into components whose sizes (number of vertices) are at most half that of the origi­ nal. Since such a vertex always exists, splitting recurses at most lg(n) + 1 levels deep, generating a pseudo-tree arrangement with height at most lg(n) + 1 .

We now generalize to arbitrary graphs. Consider an ordered graph G with induced width w* . We know from theorem 4.1 that this graph can be embedded into a w* -tree with the same number of vertices. We establish how to find the appropriate vertices for splitting k-trees, thereby allow­ ing us to generalize the previously described algorithm for pseudo-tree arranging 1-trees.

A clique of size i is said to be adjacent to another clique of size i if they share i- 1 vertices. Define depth­ first search on a non-trivial k-tree to traverse adjacent k + 1 cliques instead of adjacent vertices. Figure 3 illustrates a depth-first search tree resulting from traversing a 2-tree in such a manner. We refer to such .a depth-first search tree as the clique tree of the k-tree. While there may be more than one clique tree depending on where the depth-first search begins and what tie-breaking rule is applied, any clique tree is sufficient for the upcoming claims.

Each node of the clique tree corresponds to some clique in the k -tree, and the edges represent their intercon­ nection. We now state two properties of clique trees, leaving the proofs as exercises. Given a non-trivial k-tree G with n vertices and a clique tree T of G :

• T has exactly n - k vertices.
• Given a vertex v whose removal from T leaves behind connected components of size j , the clique represented by v , when removed from G, leaves behind components of size at most j .

We next use these properties to establish the following lemma:

LEMMA 5.1: Given a non-trivial k -tree G with n vertices, there exists k + 1 vertices in G whose removal leaves behind connected components of size at most ~ .

Proof: We have already noted that a 1-tree can always be broken into components of a size at most half that of the original graph by removing a single vertex. From a clique tree T of the k -tree, we can therefore find a vertex v whose removal splits T into components of size ~ < ~ . The k + 1 vertices in the clique represented by v, when removed from the k -tree, must therefore leave behind con­ nected components of size at most ~ . D

This method for breaking apart k-trees allows us to bound the size of the cutset required for splitting arbitrary graphs and the size of the resulting components:

COROLLARY 5.2: Given an ordered graph G with induced width w * , n > w * , there exists w * + I vertices in G whose removal leaves behind components with size at most~.

Proof: Theorem 4.1 tells us we can embed the graph into a w * -tree with the same number of vertices. Because n > w*, the w* -tree is non-trivial and the claim thus follows immediately from lemma 5.1 . D

We lastly apply the above fact to define a pseudo­ tree arrangement procedure, thereby allowing a bound on pseudo-tree height.

THEOREM 5.3: Given an ordered graph with induced width w*, there exists a pseudo-tree arrangement of the graph with h s; (w* + 1) (lgn + 1).

Proof: For n = w*, the claim is trivially satisfied by linearly arranging the vertices. Otherwise, by Corollary 5.2, we can find w * + 1 vertices whose removal leaves behind components with less than half the vertices of the original graph. We can use such a set to form the first w* + I levels of a pseudo-tree. The resulting components must have induced width of w* or less (they are simply subgraphs of the original graph). Thus, the remaining variables can be pseudo-tree arranged by applying the procedure recursively on each component. A new pseudo-tree branch is thereby spawned for each remaining component as is done by the heuristic pseudo-tree arrangement procedure from Section 2.

Now, each stage of the recursion leaves behind components whose size are at most half that of the previous graph. Therefore, recursion depth can be bounded by lg(n) + 1 . Since each level of the recursion adds at most

• w * + I new levels to the tree, the resulting pseudo tree has height at most ( w* + I) (lg(n) + 1) . 0

Theorem 5.3 tells us we can always make the expo­ nent in the complexity function of pseudo-tree backtrack within a logarithmic factor of that of the best exponential space-consuming schemes. Our proofs are constructive and describe a polynomial time-bounded procedure for accom­ plishing the task. While we did not describe a (polynomial time) procedure for finding the k-tree embedding, such a procedure appears in [Freuder, 90].

6 Conclusions

We have demonstrated that while the best structure-based techniques require exponential space, they are capable of bounding worst-case performance only slightly better than pseudo-tree search, a simple polynomial space-bounded scheme. Attempting to trade space for time is therefore of limited benefit. Interestingly, we have a similar case with respect to average case performance as well. For example, Frost and Dechter [ 1994] have found that algorithms per­ forming unlimited constraint recording during search (thereby consuming exponential space) barely outperform polynomial space-bounded constraint recording algorithms.

We lastly note the open problem of either (a) find­ ing a polynomial space algorithm that runs in time exponen­ tial in induced width, or (b) proving no such algorithm exists. Current approaches for achieving the runtime bound fundamentally require exponential space since they record high-arity constraints or generate all solutions to certain sub­ problems. On the other hand, proving no such algorithm exists seems like a P = N P related task. We therefore feel that solving the problem will be difficult if not impossible.