In this paper we propose a family of algo rithms combining tree-clustering with condi tioning that trade space for time. Such algo rithms are useful for reasoning in probabilis tic and deterministic networks as well as for accomplishing optimization tasks. By ana lyzing the problem structure it will be possi ble to select from a spectrum the algorithm that best meets a given time-space specifica tion. Topology-based algorithms for constraint satisfac tion and probabilistic reasoning fall into two distinct classes. One class is centered on tree-clustering, the other on cycle-cutset decomposition. Tree-clustering involves transforming the original problem into a tree like problem that can then be solved by a specialized tree-solvin g. algorithm [Mackworth and Freuder, 1985; Pearl, 1986j. The tree-clustering algorithm is time and space exponential in the induced width (also called tree width) of the problem's graph. The transforming algo rithm identifies subproblems that together form a tree, and the solutions to the subproblems serve as the new values of variables in a tree metalevel problem. The metalevel problem is called a join-tree. The cycle-cutset method exploits the problem's struc ture in a different way. A cycle-cutset is a subset of the nodes in a graph which cuts all of the graph's cy cles. A typical cycle-cutset method enumerates the possible assignments to a set of cutset variables and, for each cutset assignment, solves (or reasons about) a tree-like problem in polynomial time. The overall time complexity is exponential in the size of the cycle cutset [Dechter, 1992] . Fortunately, enumerating all the cutset's assignments can be accomplished in linear space. Since the space complexity of tree-clustering can severely limit its usefulness, we investigate the ex tent to which its space complexity can be reduced, while reasonable time complexity guarantees are main tained. Is it possible to have the time guarantees of clustering while using linear space? On some problem instances, it is possible. Specifically, on those problems whose associated graph has a tree width and a cutset of comparable sizes (e.g., on a ring, the cutset size is 1 and the tree width is 2, leading to identical time bounds). In general, however, it is probably not pos sible, because in general the minimal cycle-cutset of a graph can be much larger than its tree width, namely, r $ c + 1, where cis the minimal cycle-cutset and r is the tree width. Furthermore, we conjecture that any algorithm that has a time bound that is exponential in the tree-width will, on some problem instances, require exponential space in the tree width. The space complexity of tree-clustering can be bounded more tightly using the separator width, which is defined as the size of the maximum subset of vari ables shared by adjacent subproblems in the join-tree. Our initial investigation employs separator width to control the time-space tradeoff. The idea is to com bine adjacent subproblems joined by a large separator into one big cluster so that the remaining separators are of smaller size. Once a join-tree with smaller sep arators is generated, its potentially larger clusters can be solved using the cycle-cutset method. We will develop such time-space tradeoffs for belief network processing, constraint processing, and opti mization tasks, yielding a sequence of algorithms that can trade space for time. With this characterization it will be possible to select from a spectrum of algorithms the one that best meets some time-space requirement. Algorithm tree-clustering and cycle-cutset decomposi tion are two extremes in this spectrum. We introduce the ideas using belief networks (section 2) and then show how they are applicable to con straint networks (section 3) and to optimization prob lems (section 4). The observation that methods based on condition ing are inferior time-wise and superior space-wise in
In REF , Dechter and El Fattah present a time-space tradeoff scheme.
Topological Parameters for Time-Space Tradeoff
ArXiv
ArXiv
Computer Science Mathematics