4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ As i understand your conditions, Complete graph satisfies this condition and is not of bounded tree width. $\endgroup$ – Saeed Jan 6 '14 at 22:00
  • $\begingroup$ @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. $\endgroup$ – seteropere Jan 7 '14 at 3:47
  • $\begingroup$ 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. $\endgroup$ – a3nm Nov 17 '15 at 1:11

Your Answer

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

Browse other questions tagged or ask your own question.