Bag-Connected Tree-Width: A New Parameter for Graph Decomposition.
Philippe Jégou, Cyril Terrioux · ISAIM · 2014
For solving constraints networks (CSPs), (tree-)decomposition methods have shown their practical interest. But for the problem of computing tree-decompositions, the literature (coming from AI or from Mathematics) has concentrated the work on a single parameter, the tree-width. Nevertheless, experimental studies have shown that when a decomposition is used to solve a CSP, other parameters must also be considered. For example, it has been observed that in some cases, bad decompositions w.r.t. their width can be more efficient for the resolution of the underlying CSP. One of the explanations of this phenomenon is related to the structure of the clusters appearing in decompositions. For example, in this paper, we show experimentally that some clusters can have several connected components when we try to minimize the width to achieve “good” decompositions. Unfortunately, this lack of connectedness may lead the solving method to spend much effort to solve the subproblems related to these non-connected clusters, by passing many times from a connected component to another. Clearly, this can be a real drawback for globally solving a CSP in terms of time efficiency and memory space. To avoid this kind of problem, we introduce here a new graph parameter called Connected TreeWidth which considers tree decompositions for which each cluster is connected. We show that computing such optimal decompositions is an NP-hard problem. So, we propose a polynomial time algorithm to find such decompositions, but obviously, without guaranteeing optimality.