A New Method for Computing Suitable Tree-Decompositions with Respect to Structured CSP Solving
Cédric Pinto, Cyril Terrioux · 2008
The tree-decomposition notion plays a central role in the frame of the structured CSP solving. On the one hand, it is exploited in many methods like tree-clustering, BTD or cyclic-clustering (CC). It then leads to theoretical time complexity bounds among the best ones. On the other hand, it is often used as a preliminary step for computing a hypertree-decomposition. Unfortunately, finding the best tree-decomposition is a NP-hard problem. So heuristic methods are classically used for computing tree-decompositions. They mostly rely on triangulations of graphs. Sometimes, this approach by triangulation can lead to a rough identification of the structure. Such a drawback can be avoided by considering a cutset such that the remaining problem corresponds to a set of tree-decompositions. In this article, from a cutset and the corresponding set of tree-decompositions, we propose a new method for computing a suitable tree-decomposition w.r.t. CSP solving. Thanks to this approach, we can exploit BTD on the resulting tree-decomposition instead of CC on the cutset and the corresponding set of tree-decompositions. Then, unlike CC, it allows to fully exploit the informations recorded during the search, what leads to avoid some redundancies in the search space. In practice, the first empirical results are very promising since BTD with a tree-decomposition computed with the proposed method outperforms BTD with a tree-decomposition based on triangulation and some other classical algorithms.