TODO - induced width weird example
does tree-width = induced-width?
tree-width
- is based on a tree decomposition
- its value is equal to the size of its maximum node-set minus 1
induced-width
- is based on an induced-graph relative to a node ordering
- its value is equal to the node with the maximum number of parents
a primal graph with no cycles it has:
- tree-width = 1 = induced-width
the question is, given an arbitrary primal graph does the following hold:
- tree-width = induced-width
Instructor Response
Induced width is the same as tree width. Here are some important terms:
- The treewidth (or width or induced width) of an order equals the maximum cluster size minus 1. (Recall that the clusters are obtained by running bucket elimination schematically.)
- The treewidth (or induced width) of a graph is the minimum treewidth over all possible orderings.
In many research papers, the authors will use the term “width” for an order and treewidth or induced width for the graph
Minimal Tree-Width = Minimal Induced-Width
The minimal tree-width is identical to the minimal induced-width of a graph
Experiment
based on some experiments, I believe tree-width = induced-width
given the primal graph below and its chosen node ordering (A B C E D F):
- the tree decomposition has tree-width = 2
- the induced graph has induced-width = 2
the tree decomposition was formed the purple arrows in the bucket elimination algorithm
the induced graph was formed with extended graph as input:
- the extended graph was a combination of pseudo tree and primal graph
- the pseudo tree was formed with the structure of the tree decomposition
