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$
3
  • $\begingroup$ As i understand your conditions, Complete graph satisfies this condition and is not of bounded tree width. $\endgroup$
    – Saeed
    Jan 6, 2014 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, 2014 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, 2015 at 1:11

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.