Structural Restrictions
Bounding the width of a decomposition method by a constant creates a structural restriction, that is, it limits the possible scopes of constraints, but not their relations. The complementary way for obtaining tractable subclasses of constraint satisfaction is by placing restriction over the relations of constraints; these are called relational restriction, and the set of allowed relations is called constraint language.
If solving problems having a decomposition width bounded by a constant is in P, the decomposition leads to a tractable structural restriction. As explained above, tractability requires that two conditions are met. First, if the problem has width bounded by a constant then a decomposition of bounded width can be found in polynomial time. Second, the problem obtained by converting the original problem according to the decomposition is not superpolynomially larger than the original problem, if the decomposition has fixed width.
While most tractable structural restrictions derive from fixing the width of a decomposition method, others have been developed. Some can be reformulated in terms of decomposition methods: for example, the restriction to binary acyclic problem can be reformulated as that of problem of treewidth 1; the restriction of induced width (which is not defined in terms of a decomposition) can be reformulated as tree clustering.
An early structural restriction (that later evolved into that based on induced width) is based on the width of the primal graph of the problem. Given an ordering of the nodes of the graph, the width of a node is the number of nodes that join it and precede it in the order. However, restricting only the width does not lead to a tractable restriction: even restricting this width to 4, establishing satisfiability remains NP-complete. Tractability is obtained by restricting the relations; in particular, if a problem has width and is strongly -consistent, it is efficiently solvable. This is a restriction that is neither structural nor relational, as it depends on both the scopes and the relations of the constraints.
Read more about this topic: Decomposition Method (constraint Satisfaction)
Famous quotes containing the word structural:
“The reader uses his eyes as well as or instead of his ears and is in every way encouraged to take a more abstract view of the language he sees. The written or printed sentence lends itself to structural analysis as the spoken does not because the reader’s eye can play back and forth over the words, giving him time to divide the sentence into visually appreciated parts and to reflect on the grammatical function.”
—J. David Bolter (b. 1951)