Content deleted Content added
Vegaswikian (talk | contribs) Disambiguated: tractable → tractable problem; Unlinked: Primal graph (2); Help needed: Primal graph |
→Cycle cutset: add link to Feedback Vertex Set |
||
Line 77:
[[Image:Cutset-4.svg|right|frame|Choosing the node b as the root, this is the tree similar to the ones created by the other decomposition methods]]
Such a decomposition does not fit in the scheme of the other decompositions because the result of the decomposition is not a tree, but rather a set of variables (those of the cutset) and a tree (formed by the variables not in the cutset). However, a tree like those generated by the other decomposition methods can be obtained from the tree that results from removing the cutset; this is done by choosing a root, adding all variables of the cutset to all its nodes, and the variables of each node to all its children. This results in a tree whose maximal number of variables associated with a node is equal to the size of the cutset plus two. Apart from the addition of two, this is the width of the decomposition, which is defined as the number of variables in the considered cutset.
Unfortunately, determining the minimum set to remove is [[Feedback vertex set| an NP-Hard problem]].
===Tree decomposition===
| |||