Decomposition Method (constraint Satisfaction) - Comparison

Comparison

The width of instances is a form of efficiency of decomposition methods. Indeed, given that problems can be solved from decompositions of fixed width, the less the width according to a decomposition, the more the instances that can be solved efficiently using that decomposition.

Some decompositions use the number of variables of a node (or a similar amount) as the width. Others do not: cycle hypercutset, hinge decomposition, query decomposition, hypertree decomposition, and generalized hypertree decomposition associate constraints (or their scopes in form of hyperedges) with nodes, and include the number of constraints associated to a node in the width. This can be a significant save in terms of width. Indeed, problems with a single constraint on variables can only be decomposed in a tree with a single node. This node can be associated with the variables or with the single constraint. Counting the number of variables leads to width, while counting the number of constraints leads to width .

The comparison between all other decomposition methods is based on generalization and beating. Generalization means that every problem having width according to a method has width bounded by for a fixed . Beating means that there are classes of problems that have fixed width according to a decomposition method but not according to another. The following are the results for arbitrary problems, where query decomposition is not considered:

• hypertree decomposition generalizes and beats all other methods
• hinge decomposition enhanced with tree clustering generalizes and beats both hinge decomposition and tree clustering
• tree clustering is equivalent to tree decomposition (on the primal graph)
• both hinge decomposition and tree clustering generalize and beat biconnected components
• cycle cutset (on the primal graph) is generalized and beaten by both cycle hypercutset and tree clustering

It can also be shown that the tree clustering width is equal to the induced width of the problem plus one. The algorithm of adaptive consistency, which is polynomial for problem of fixed induced width, turns problems into equivalent ones in the same way as the first step of tree clustering.