An Algorithmic Framework for Decomposing Constraint Networks

Depending on the nature of CSP instances to consider, the decomposition methods offer an approach often efficient for the solving, the counting of solutions or the optimization. So, the community has focused a large part of its efforts on the design of algorithms aiming to find the best decompositions, i.e. ones which minimize the width of the decomposition, the fundamental parameter in terms of theoretical complexity. In this frame, the heuristic Min-Fill constitutes the reference method. In this paper, we introduce an algorithmic framework for network decomposition aiming to improve Min-Fill. It computes tree-decompositions based on a traversal of the graph using properties related to separators and their associated connected components. Its time complexity is lower than the one of Min-Fill. Moreover, it permits the implementation of several heuristics which can guide the decomposition over several criteria like the size of the clusters, the size of the separators, the connectivity of the clusters, which are particularly relevant to improve the efficiency of the solving by decomposition methods. Experiments assess this new approach and demonstrate its practical advantages for decomposing and solving constraint networks.