MINIMUM TREE WIDTH

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A tree decomposition, i.e., a pair $\left(\{X_i:i\in I\},T\right)$ where $T=\left(I,F\right)$ is a tree and $\{X_i\}$ is a collection of subsets of V, such that

  1.

  $\bigcup_{i\in I} X_i=V$,

  2.

  for any $(v,w)\in E$, there exists an $i\in I$ with $u,v\in X_i$,

  3.

  for any $v\in V$, the set $\{i\in I: v\in X_i\}$ forms a connected subtree of T.

• MEASURE: The tree width of the tree decomposition, i.e., $\max_{i \in I} \vert X_i\vert-1$.

  
  

• Good News: Approximable within $O(\log \vert V\vert)$ [88].

• Bad News: There is no polynomial-time algorithm with an absolute error guarantee of $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ [88].

• Comment: MINIMUM PATH WIDTH, the variation in which T is a path, is approximable within $O(\log^2 \vert V\vert)$ and has the same negative bound. Similar problems with the same positive and negative results are MINIMUM ELIMINATION TREE HEIGHT and MINIMUM FRONT SIZE [88].