Next: MINIMUM GRAPH INFERENCE Up: Miscellaneous Previous: MINIMUM METRIC DIMENSION Index

### MINIMUM TREE WIDTH

- INSTANCE: Graph .

- SOLUTION: A tree decomposition, i.e., a pair where is a tree and {Xi} is a collection of subsets of V, such that
  1.
    ,

  2.
    for any , there exists an with ,

  3.
    for any , the set forms a connected subtree of T.

- MEASURE: The tree width of the tree decomposition, i.e., .

- Good News: Approximable within [81].

- Bad News: There is no polynomial-time algorithm with an absolute error guarantee of for any [81].

- Comment: MINIMUM PATH WIDTH, the variation in which T is a path, is approximable within and has the same negative bound. Similar problems with the same positive and negative results are MINIMUM ELIMINATION TREE HEIGHT and MINIMUM FRONT SIZE [81].