Типичная твердость дерева разложения?

Разложение дерева сложно в худшем случае, но жадный метод кажется почти оптимальным в небольших реальных сетях.

1. Известно ли что-нибудь о сложности разложения дерева «типичного» экземпляра некоторого класса графов?
2. Есть ли пример семейства графов, где жадные методы разложения дерева плохо работают?

Я только что натолкнулся на соответствующую статью - Kloks / Boedlander: «Только у немногих графов ограниченная ширина дерева». Они показывают, что почти все графы с вершинами и δ n ребрами имеют ширину дерева порядка n ϵ , ϵ = δ - $n$$\delta n$$n^\epsilon$$\epsilon=\frac{\delta-1}{\delta+1}$$\delta=3$$\sqrt{n}$

Таким образом, даже если жадный метод нашел наилучшую декомпозицию для всех графов, результирующий алгоритм все равно был бы невероятно медленным для типичных графов.