12
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ you should add it as an answer: there's even a badge for accepting your own answer $\endgroup$ – Suresh Venkat Jan 8 '11 at 2:54
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.