Next: MINIMUM GRAPH INFERENCE
Up: Miscellaneous
Previous: MINIMUM METRIC DIMENSION
Index
 INSTANCE:
Graph
.
 SOLUTION:
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.
 MEASURE:
The tree width of the tree decomposition, i.e.,
.
 Good News:
Approximable within
[88].
 Bad News:
There is no polynomialtime algorithm with an absolute error guarantee of
for any
[88].
 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
[88].
Viggo Kann
20000320