GT50 M INIMUM T REE W IDTH

     
• I NSTANCE : Graph .
• S OLUTION : A tree decomposition, i.e., a pair where is a tree and 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 .

• M EASURE : The tree width of the tree decomposition, i.e., .

• Good News: Approximable within [ 57 ].
• Bad News: There is no polynomial-time algorithm with an absolute error guarantee of for any [ 57 ].
• Comment: The 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 [ 57 ].