Combining Breadth-First and Depth-First Strategies in Searching for Treewidth

1 Introduction

Breadth-first and depth-first search are basic search strategies upon which many other search algorithms are built. Given the very different way in which they order node expansions, it is not obvious that they can be combined in the same search algorithm. In this paper, we describe an approach to integrating these two strategies in a single algorithm that combines the complementary strengths of both. To illustrate the benefits of this approach, we use the treewidth problem as an example.

The treewidth of a graph (also known as the induced treewidth) is a measure of how similar the graph is to a tree, which has a treewidth of 1. A completely connected graph is least similar to a tree, and has a treewidth of n - 1, where n is the number of vertices in the graph. Most graphs have a treewidth that is somewhere in between 1 and n - 1.

There is a close relationship between treewidth and vertex elimination orders. Eliminating a vertex of a graph is defined as follows: an edge is added to every pair of neighbors of the vertex that are not adjacent, and all the edges incident to the vertex are removed along with the vertex itself. A vertex elimination order specifies an order in which to eliminate all the vertices of a graph, one after another. For each elimination order, the maximum degree (i.e., the number of neighbors) of any vertex when it is eliminated from the graph is defined as the width of the elimination order. The treewidth of a graph is defined as the minimum width over all possible elimination orders, and an optimal elimination order is any order whose width is the same as the treewidth.

Many algorithms for exact inference in Bayesian networks are guided by a vertex elimination order, including Bucket Elimination [Dechter, 1999], Junction-tree elimination [Lauritzen and Spiegelhalter, 1988], and Recursive Conditioning [Darwiche, 2001]. In fact, the complexity of all of these algorithms is exponential in the treewidth of the graph in-

Eric A. Hansen

Dept. of Computer Science and Engineering Mississippi State University Mississippi State, MS 39762 hansen@cse.msstate.edu

duced by the network. For these algorithms, use of a suboptimal elimination order leads to inefficiency, and improving an elimination order by even small amount can result in large computational savings. Solving the treewidth problem exactly, and finding an optimal elimination order, allows these algorithms to run as efficiently as possible.

2 Previous work

Finding the exact treewidth of a general graph is an NPcomplete problem [Arnborg et al., 1987]. One approach to finding the exact treewidth is depth-first branch-and-bound search in the space of vertex elimination orders [Gogate and Dechter, 2004]. However, Dow and Korf [2007] showed that best-first search can significantly outperform depth-first branch-and-bound search by avoiding repeated generation of duplicate search nodes.

In the search space of the treewidth problem, each node corresponds to an intermediate graph that results from eliminating a set of vertices from the original graph. Figure 1 shows the treewidth search space for a graph of 4 vertices. Each oval represents a search node that is identified by the set of vertices eliminated so far from the original graph. A path from the start node (which has an empty set of eliminated vertices) to the goal node (which has all vertices eliminated) corresponds to an elimination order, and there is a one-to-one mapping from the set of elimination orders to the set of paths from the start to the goal node. Although there are n! different elimination orders for a graph of n vertices, there are only 2n distinct search nodes. This is because different ways of eliminating the same set of vertices always arrive at the same intermediate graph [Bodlaender et al., 2006], and there is only one distinct intermediate graph for each combination (as opposed to permutation) of the vertices. Depth-first branch-and-bound search treats the search space as a tree with n! distinct states instead of a graph with only 2n states. The faster performance of best-first treewidth search reflects the difference in size between a search tree and a search graph [Dow and Korf, 2007].

Unfortunately, the scalability of best-first (treewidth) search is limited by its memory requirements, which tend to grow exponentially with the search depth. To improve scalability, Dow and Korf use a memory-efficient version of bestfirst search called breadth-first heuristic search [Zhou and Hansen, 2006], which, like frontier search [Korf et al., 2005], only stores the search frontier in memory and uses a divideand-conquer approach to reconstruct the solution path after the goal is reached. In fact, they use a variant of breadth-first heuristic search, called SweepA* [Zhou and Hansen, 2003], that exploits the fact that the search graph for the treewidth problem is a partially ordered graph. A partially ordered graph is a directed graph with a layered structure, such that a node in one layer can only have successors in the same layer or later layers. This allows layers to be removed frommemory after all their nodes are expanded. SweepA* expands all the nodes in one layer before considering any nodes in the next layer, and uses an admissible heuristic and an upper bound to prune the search space.

Besides exploiting the layered structure of the search graph using SweepA*, there is another important way in which the search algorithm of Dow and Korf limits use of memory. Because the size of an intermediate graph can vary from several hundred bytes to a few megabytes, storing an intermediate graph at each search node is impractical for all but the smallest problems. Instead, Dow and Korf store with each search node only the set of vertices that have been eliminated so far. Each time a node is expanded, its corresponding intermediate graph is generated on-the-fly by eliminating from the original graph those vertices stored with the node. While this approach is space-efficient, it incurs the overhead of intermediate graph generation every time a node is expanded. For large graphs, this overhead is significant. In this paper, we describe a technique that eliminates much of this overhead.

3 Meta search space

To reduce the time overhead of intermediate graph generation, we describe a search algorithm that does not generate the intermediate graph from the original graph at the root node of the search space. Instead, it generates it from the intermediate graph of a close neighbor of the node that is being expanded. The advantage is that the intermediate graph of a close neighbor is already very similar, and so there is much less overhead in transforming it into a new intermediate graph. The simplest way to find the node's closest neighbor is by computing shortest paths from a node to all of its neighbors and picking the closest one. But at first, this does not seem to work for the treewidth problem, since its state space is a partially ordered graph in which the distance between any pair of nodes at the same depth is infinite.

Our idea is to measure the distance between a pair of nodes in a meta search space, instead of the original search space. A meta search space has exactly the same set of states as the original search space, but is augmented with a set of meta actions that can transform one node into another in ways not allowed in the original search space. For example, a meta action for the treewidth problem can be an action that "uneliminates" a vertex by reversing the changes made to a graph when the vertex was eliminated. For the treewidth problem augmented with the "uneliminate" meta action, its search graph is an undirected version of the graph shown in Figure 1. In this new graph, called a meta search graph, actions (i.e., edges) can go back and forth between a pair of adjacent nodes, and this allows us to generate the intermediate graph of a node from another node at the same depth. This is very useful for breadth-first heuristic search, which expands nodes in order of their depth in the search space.

Since a node is uniquely identified by the set of vertices eliminated, we use the same lower-case letter (e.g., n, u, and v) to denote both a node and a set of eliminated vertices in the rest of this paper. To implement the "uneliminate" meta action, each edge of the meta search graph is labeled by a tuple 〈u, v,ΔE+,ΔE-〉, where u (v) is the set of vertices eliminated so far at the source (destination) node of the edge, and ΔE+ (ΔE-) is the set of edges added to (deleted from) the graph when the vertex in the singleton set v \ u is eliminated. Let Gn = 〈Vn, En〉 be the intermediate graph associated with node n. The task of adding a previously-eliminated vertex back to the graph can be expressed formally as: given Gv = 〈Vv , Ev〉 and e = 〈u, v, ΔE+, ΔE-〉, how to compute Gu = 〈Vu,Eu〉? Since all the changes are recorded with the edge e, one can reconstruct Gu = 〈Vu, Eu〉 as follows,

That is, by adding (deleting) the edges that have been previously deleted (added) to the graph, the "uneliminate" meta action can undo the effects of an elimination action in the original search space.

In general, adding meta actions can turn directed search graphs into undirected graphs. This guarantees that any changes made to the current state (e.g., the intermediate graph) is reversible, creating a graph with the following appealing property: for any two states reachable from the start state, there is always a path that maps one into the other. This property allows a search algorithm to generate the state representation of a node from any stored node, because if all actions are deterministic, then a state s′ is uniquely identified by another state s plus a path from s to s′ . If it takes less space to represent a path between s and s′ , then this approach to state encoding can save memory, although at the cost of some computational overhead.

For the treewidth problem, this means the intermediate graph of a node can be generated from any node instead of only from the node's direct ancestors, such as the start node. Thus, one only needs to maintain a single intermediate graph, which can be modified to become the intermediate graph for any node in the search space. An interesting question is how to minimize the overhead of generating the intermediate graph from one node to another. The answer depends on the search strategy, because ultimately our goal is to minimize the overhead of expanding not just a single node but a set of nodes.

4 Frontier decision tree

The solution we propose is to use an ordered decision tree to store the set of frontier nodes at the current depth of breadthfirst heuristic search as the leaves of the decision tree. Unlike explicit-state search methods, this approach can be viewed as a variant of symbolic search in which the state-representation similarities among a set of nodes are retained in the decision tree and exploited by the search algorithm.

A decision tree is defined as a rooted tree in which every non-leaf node is a decision node that performs a test on a variable, the value of which is then used to determine recursively the next decision node until a leaf node is reached. A decision tree is commonly used to represent a discrete function over a set of variables. For the treewidth problem, these are Boolean variables, one for each vertex. A Boolean variable has the value of true if its corresponding vertex has been eliminated.

To make operations on decision trees more efficient, an ordering constraint is usually enforced that requires the order in which variables are tested to be the same on any path from the root to a leaf node. The resulting data structure is called an ordered binary decision tree, and an example is shown in Figure 2. In this example, variables are tested in increasing order of vertex number: 1, 2, 3, then 4. A solid (dashed) edge represents a truth (false) assignment to the variable being tested at the source node of the edge. A leaf node corresponds to a complete assignment to all the variables, and there is a oneto-one mapping from the set of leaf nodes shown in Figure 2 to the set of search nodes shown in Figure 1. From now on, we call a decision tree that stores the frontier nodes of a search graph in this way a frontier decision tree.

To support meta actions, each edge of the frontier decision tree stores "undo" information as needed by Equations (1) and (2). Note that for an undirected search space, there is no need to store such information.

Variable ordering We use a frontier decision tree in order to reduce the time overhead for regenerating the intermediate graph from the root node. But this must be weighed against the space overhead for storing the decision tree.

An important way to save space in a frontier decision tree is to find a good ordering of the variables, which affects the number of decision nodes needed to represent a set of frontier nodes. While finding an optimal ordering is a hard combinatorial optimization problem in itself, good orders can often be found quickly by using simple heuristics. We tried three variable-ordering heuristics, the details of which are described in the computational results section.

Figure 3: A partial binary decision tree in which the currently expanding nodes are stored as full-depth leaves and non-expanding nodes as shallow-depth leaves.

A decision node is useless if it does not lead to any leaf node. To prune these useless decision nodes, we store a leafnode counter at each decision node. Each time a leaf node is deleted, all of its ancestor decision nodes decrease their leafnode counters by one, and a decision node is deleted as soon as its leaf-node counter reaches zero. Once useless nodes are pruned, the (asymptotic) space complexity of a frontier decision tree is the same as that of an explicit-state representation of the same nodes. In practice, however, their actual memory requirements can differ by a constant, since a node in an explicit-state search can be compactly represented as a bit-vector; whereas a decision node needs more space to store, even though the total number of decision nodes is usually much less than the total number of bits needed to encode the same nodes, due to state aggregation in a decision tree.

Partial frontier decision tree To further reduce the space overhead of using a frontier decision tree, we introduce a hybrid data structure called a partial frontier decision tree that combines the complementary strengths of both symbolic and explicit-state representations. The idea is to generate the decision nodes of the tree on the fly as its leaf nodes are expanded, so that only a (small) subset of frontier nodes that are selected for expansion need to be represented in decision tree form. A partial decision tree has two kinds of leaves; a full-depth leaf, which is uniquely identified by a complete path whose length equals the number of vertices in the original graph, and a shallow-depth leaf, which is identified by an incomplete path. Figure 3 shows an example of a partial frontier decision tree in which only the currently expanding nodes are represented as full-depth leaves in the tree. Because an incomplete path can lead to a set of shallow-depth leaves, a bit-vector is stored at each frontier node to specify its "remaining" path.

Structured duplicate detection By itself, a partial frontier decision tree cannot significantly reduce the overhead of generating the intermediate graphs, because it still needs a search strategy that can exploit the similarities among a set of nodes. For this reason, we use a technique called structured duplicate detection (SDD) [Zhou and Hansen, 2004b]. Nodes in SDD are partitioned into buckets, one for each abstract state defined by a state-space projection function. To exploit locality, SDD expands nodes in the same bucket consecutively. In the case of a partial decision tree, SDD expands full-depth leaves first, since their decision-tree representation is complete. Upon selecting a new bucket for expansion, SDD converts all its shallow-depth leaves into full-depth leaves before expanding them. Since the conversion is done automatically by SDD, the search algorithm has the "illusion" that it is working with the full (instead of partial) frontier decision tree. Thus, for clarity, we will ignore the difference between full and partial frontier decision trees, until we come back to it in the computational-results section.

5 Depth-first search in frontier decision tree

The purpose of using an ordered binary decision tree to store the set of frontier nodes is twofold. First, it reveals the similarities among the frontier nodes, because nodes with the same prefix (according to the test ordering) share the same ancestor node in the decision tree. For example, because nodes {1, 2, 3} and {1, 2, 3, 4} share the same prefix {1, 2, 3}, they have the same parent node in the decision tree. On the other hand, because nodes {∅} and {1, 2, 3, 4} have nothing in common, their common ancestor is only the root node. Second, the tree topology guarantees there is a unique path from the root to a leaf node. This facilitates the use of a tree-search algorithm such as depth-first search to determine the order in which frontier nodes are expanded.

It is well-known that depth-first search has excellent memory-reference locality. This is particularly well suited for decision trees, since a depth-first search of a decision tree always visits nodes with the same prefix before visiting nodes with different prefixes, and the longer the prefix shared by two nodes, the closer they will be visited in depth-first search. For the treewidth problem, this means that if two nodes have similar intermediate graphs, they will be expanded close to each other, and the more similar their intermediate graphs, the closer together they will be expanded. To minimize the intermediate-graph generation overhead for the entire set of frontier nodes at the current search depth, we use depth-first traversal of the decision tree, which visits all leaf nodes of the decision tree. Thus, our treewidth algorithm adopts a hybrid search strategy that uses depth-first traversal in a symbolic (e.g., decision-tree) representation of the (meta) search graph to determine the order of node expansions for the current depth of breadth-first heuristic search (or nodes with the same minimum f -cost in the case of A*). The depth-first search aspect essentially serves as a tie-breaking strategy in breadthfirst (or best-first) search to improve its memory-reference locality; in the case of treewidth computation, it also reduces the overhead of generating the intermediate graphs.

Example Figure 4 shows an example howdepth-first search can reduce the intermediate-graph generation overhead in breadth-first heuristic search for treewidth. Suppose the three leaves shown in the figure are the frontier nodes of breadthfirst heuristic search, and the intermediate graph has already been generated for node {1, 3, 4}. Depth-first search will visit node {1, 2, 4} next, and then node {1, 2, 3}. A sequence of dark (solid and dashed) arrows represents the order in which actions are taken to "migrate" the intermediate graph from node {1, 3, 4} to node {1, 2, 4} and then to node {1, 2, 3}. A solid dark arrow moving towards the leaf (root) represents an action that eliminates (uneliminates) a vertex. Dashed arrows represent no-op actions that simply move an intermediate graph around in the decision tree without changing its content. The action sequence shown in Figure 4 starts with a meta action (shown as a dark, upward arrow from node {1, 3, 4}) that "uneliminates" vertex 4 from the intermediate graph G{1,3,4} in order to generate G{1,3}. Then vertex 3 is "uneliminated" to generate G{1}. Next, vertex 2 is eliminated from the intermediate graph to generate G{1,2}, and then vertex 4 is eliminated to arrive at G{1,2,4}. To migrate from node {1, 2, 4} to node {1, 2, 3}, vertex 4 is "uneliminated" and then vertex 3 is eliminated to generate the intermediate graph G{1,2,3}. Because an "uneliminate" meta action does not need to check for connectivity between all possible pairs of a vertex's neighbors, it is usually much cheaper than eliminating a vertex. Thus, we only count the number of times an elimination action is performed as overhead. In this example, there are altogether 3 elimination actions. For comparison, generating the intermediate graphs for nodes {1, 2, 3} and {1, 2, 4} from the root node would require 6 elimination actions (3 for node {1, 2, 3} and 3 for node {1, 2, 4}), which is (almost) twice as expensive.

Note that the benefit of our approach increases as the search frontier moves further away from the root node. For example, if the three leaf nodes in Figure 4 are a hundred elimination steps away from the root node, then it will take about 200 elimination actions to regenerate the intermediate graphs for nodes {1, 2, 4} and {1, 2, 3}; whereas it still takes the same number of elimination actions (3) with our approach, no matter how deep these nodes are, as long as the intermediate graph has just been generated for a node ({1, 3, 4} in this example) that is close by. Moreover, the overhead of elimination actions can differ significantly depending on the size and topology of the intermediate graph. Because intermediate graphs have fewer vertices as the search goes deeper, elimination actions tend to become cheaper as frontier nodes move further away from the root. In other words, the overhead of the 3 elimination actions needed in our approach is probably cheaper than 1.5% (i.e., 3/200) of the overhead incurred by generating the intermediate graphs from the root, if the overhead differences in elimination actions are accounted for.

6 Computational results

Both random graphs and benchmark graphs were used in our experiments. Given the number of vertices V , a random graph is generated by selecting a fixed number of edges E uniformly from the set of V (V - 1)/2 possible edges. All experiments were run on a machine with two Intel 2.66 GHz Xeon dual-core processors and 8 GB of RAM, although the search algorithm never used more than 4 GB of RAM; no multi-threading parallelization was used. As in previous studies [Gogate and Dechter, 2004; Dow and Korf, 2007], the same admissible heuristic called MMD+(least-c) [Bodlaender et al., 2004] was used in all our experiments.

Recall that the order in which decision variables are tested can affect the size of an ordered decision tree. We tested three variable-ordering heuristics: (a) a random ordering heuristic, (b) a minimum-degree-vertex-first heuristic, which orders the variables in increasing degrees of their corresponding vertices, and (c) a maximum-degree-vertex-first heuristic, which does the opposite. Results indicate that the random ordering and minimum-degree-vertex-first heuristics store on average 40% and 135% more decision nodes than the maximumdegree-vertex-first heuristic in solving random graphs, respectively. Thus, the maximum-degree-vertex-first heuristic was used for all the experimental results reported here.

Next we studied two different strategies for caching the "undo" information at the edges of the frontier decision tree. The cache-until-removal strategy stores "undo" information for every edge of the decision tree until the edge is removed due to the pruning of some decision node. The cache-untilbacktrack strategy stores "undo" information until the depthfirst traversal of the decision tree backtracks from the edge to the source decision node of that edge. In other words, it only stores "undo" information along the current "stack" of the depth-first traversal. Thus, the maximum number of edges for which "undo" information is stored cannot exceed the depth of the decision tree, which is bounded by the number of vertices in the original graph. Because the memory requirements depend on the complexity of the "undo" information measured in terms of the size of ΔE+ and ΔE-, our implementation keeps track of the maximum number of edges included in all such ΔE sets, which reflects accurately the total amount of memory used for storing "undo" information over the entire decision tree. With the cache-until-removal strategy, the average peak number of ΔE edges cached is 7,253,520 edges. This number decreased to about 405 edges when the cache-until-backtrack strategy was used, reducing the number of ΔE edges by a factor of over 17,900 times! Surprisingly, this has little effect on the average running time of the algorithm; using the cache-until-backtrack strategy increased the average running time by less than 1.7%, which is hardly noticeable. We also compared the treewidth solution and the number of node expansions of the two caching strategies for all random graphs we tested to make sure the results are correct. Results in the rest of this section were obtained by using the cache-until-backtrack strategy only.

We used breadth-first heuristic search as the underlying search algorithm, which needs an upper bound to prune nodes with an f-cost greater than or equal to the upper bound. While an upper bound for treewidth can be quickly computed by using the minimum fill-in (min-fill) heuristic, in our experiments we used divide-and-conquer beam search [Zhou and Hansen, 2004a] which can usually find tighter upper bounds. A beam-search variant of breadth-first heuristic search, divide-and-conquer beam search (DCBS) limits the maximum size of a layer in the breadth-first search graph. When memory is full (or reaches a predetermined bound), DCBS recovers memory by pruning the leastpromising nodes (i.e, the nodes with the highest f-cost) from the Open list before it continues the search.

Using a memory bound of 64 nodes, DCBS finds the exact treewidth for 97 out of the 100 random graphs. For the remaining three graphs, its solutions are very close to the exact treewidth. When averaged over all 100 graphs, the solution found by DCBS is within 0.2% of optimality.

Table 1 shows the reduction in peak number of decision nodes stored in a partial decision tree against a full tree. For this experiment, we used a set of 100 random graphs, generated by using V = 35 and E = 140, which correspond to the most difficult set of random graphs used in [Dow and Korf, 2007]. As can be seen, there is more reduction in the peak number of decision nodes as problem difficulty increases. Further reductions are possible if a finer-grained state-space projection function is used to partition the search frontier nodes into smaller buckets in structured duplicate detection.

In our next experiment, we used V = 40 and E = 120

to generate a set of more difficult random graphs than previously used. The results are shown in Table 2, which compares two different approaches to generating the intermediate graphs, one by eliminating vertices from the original graph, as in [Dow and Korf, 2007], and the other by modifying the intermediate graph of a neighboring node. Both approaches use BFHS as their underlying search algorithm. Note that the ratio by which the second approach improves on the first one increases with the hardness of the instance. For example, the average speedup ratio for the 5 easiest instances (shown above the horizontal line) is 1.3; for the 5 hardest instances (shown below the horizontal line), it is 3.1. The reason our hybrid algorithm performs even better on hard instances is that the more nodes are expanded, the easier it is to find a neighbor whose intermediate graph closely resembles the one to be generated next.

Table 3 shows the performance of our algorithm on benchmark graphs for DIMACS graph coloring instances. Compared to published results [Dow and Korf, 2007; Gogate and Dechter, 2004], Table 3 shows improvement over the state of the art. The running time shown in Table 3 includes the CPU seconds for computing the upper bound using DCBS.

7 Conclusion

We have presented a novel combination of breadth-first and depth-first search that allows a single search algorithm to possess the complementary strengths of both. While our paper focuses on the treewidth problem, many of the ideas have the potential to be applied to other search problems, especially graph-search problems with large encoding sizes, for which memory-reference locality is the key to achieving good performance. Possibilities include model checking [Clarke et al., 2000], where a large data structure that represents the current state is typically stored with each search node. As long as the similarities among different search nodes can be captured in a form that allows depth-first search to exploit the staterepresentation locality in node expansions, the approach we have described could be effective.

Finally, since our approach to reducing the memory requirements of frontier decision tree uses structured duplicate detection, it can be easily combined with an external-memory graph-search algorithm, for which time rather than memory is likely to be the main bottleneck.