Typical hardness of tree decomposition? Tree decomposition is hard in the worst case but greedy method seems to be near-optimal on small real-life networks.


Is anything known about hardness of tree decomposition of a "typical" instance of some class of graphs?
Is there example of a family of graphs where greedy methods for tree decomposition do badly?
I just came across a relevant paper -- Kloks/Boedlander's "Only few graphs have bounded tree width". They show that almost all graphs with $n$ vertices and $\delta n$ edges have treewidth on the order of $n^\epsilon$, $\epsilon=\frac{\delta-1}{\delta+1}$. For instance $\delta=3$ means typical tree-width grows as $\sqrt{n}$

So even if greedy method found the best decomposition for all graphs, the resulting algorithm would still be intractably slow for typical graphs