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.
Read more about this topic: Decomposition Method (constraint Satisfaction)
Famous quotes containing the word comparison:
“It is comparison than makes people miserable.”
—Chinese proverb.
“Away with the cant of “Measures, not men!”Mthe idle supposition that it is the harness and not the horses that draw the chariot along. No, Sir, if the comparison must be made, if the distinction must be taken, men are everything, measures comparatively nothing.”
—George Canning (1770–1827)
“We teach boys to be such men as we are. We do not teach them to aspire to be all they can. We do not give them a training as if we believed in their noble nature. We scarce educate their bodies. We do not train the eye and the hand. We exercise their understandings to the apprehension and comparison of some facts, to a skill in numbers, in words; we aim to make accountants, attorneys, engineers; but not to make able, earnest, great- hearted men.”
—Ralph Waldo Emerson (1803–1882)