# How to go from a DAG model to bounded treewidth?

I am cross posting this question from CS.SE since I believe it is research-related question.

Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps:

1. moralisation (connect variables that have the same child, drop directions)
2. triangulation (fill-in edges) i.e chordal graphs.

Are there known conditions/assumptions over $G$ under which for any junction tree $T_G$, $T_G$ will have tree width at most $k$? In other words, bounded treewidth for the triangulated graph of $G$?

• As i understand your conditions, Complete graph satisfies this condition and is not of bounded tree width. – Saeed Jan 6 '14 at 22:00
• @Saeed I am looking for conditions to bound the tree width of any junction tree resulted from the DAG $G$. I thought about bounding the in-degree of $G$, however, this seems to be a lower bound on the resulted tree width. – seteropere Jan 7 '14 at 3:47
• Triangulation is the same as chordalization (i.e., complete a graph to a chordal graph), and the treewidth of a graph is actually the minimum, over chordalizations, of the width of the chordalization, which is the size of the maximal clique size in the chordalization minus one (see e.g., digitalarchive.maastrichtuniversity.nl/fedora/get/… p17). So once $G$ was moralized, letting $w$ be the width of the moralization, the best junction tree has width $w$. As for the width of the worst chordalization, I don't know. – a3nm Nov 17 '15 at 1:11