<p>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}$</p>

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

CC BY-SA 2.5
2011-01-08T03:12:56.827Z
2011-01-08T03:12:56.827Z
Yaroslav Bulatov
<p>Tree decomposition is hard in the worst case but greedy method seems to be near-optimal on small real-life networks.</p>

<ol>
<li>Is anything known about hardness of tree decomposition of a "typical" instance of some class of graphs?</li>
<li>Is there example of a family of graphs where greedy methods for tree decomposition do badly?</li>
</ol>

CC BY-SA 2.5
2011-01-08T02:54:30.190Z
you should add it as an answer: there's even a badge for accepting your own answer
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms><treewidth>
Typical hardness of tree decomposition?
Yaroslav Bulatov
# Typical hardness of tree decomposition?

(Asked by: username_0 on 2010-12-08)

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

1. Is anything known about hardness of tree decomposition of a "typical" instance of some class of graphs?
2. Is there example of a family of graphs where greedy methods for tree decomposition do badly?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, treewidth

> **Comments:**
> **username_1**: you should add it as an answer: there's even a badge for accepting your own answer  

---

## 1 answers

### Answer by username_0 on 2011-01-08. Score: 7 | Accepted answer

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


---

