<p>I am cross posting this question from <a href="https://cs.stackexchange.com/questions/19467/how-to-go-from-a-dag-model-to-bounded-treewidth">CS.SE</a> since I believe it is research-related question.  </p>

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

<ol>
<li>moralisation (connect variables that have the same child, drop directions)</li>
<li>triangulation (fill-in edges) i.e chordal graphs. </li>
</ol>

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

CC BY-SA 3.0
2014-01-06T22:00:29.277Z
As i understand your conditions, Complete graph satisfies this condition and is not of bounded tree width.
Saeed
CC BY-SA 3.0
2014-01-07T03:47:14.583Z
@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
CC BY-SA 3.0
2015-11-17T01:11:32.663Z
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., http://digitalarchive.maastrichtuniversity.nl/fedora/get/guid:e5729e4d-247c-431d-b1ce-db84ca580e53/ASSET1 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.
Antoine Amarilli 'a3nm'
<graph-theory><treewidth>
How to go from a DAG model to bounded treewidth?
seteropere
# How to go from a DAG model to bounded treewidth?

(Asked by: username_0 on 2014-01-05)

I am cross posting this question from [CS.SE](https://cs.stackexchange.com/questions/19467/how-to-go-from-a-dag-model-to-bounded-treewidth) 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$?

**Tags:** graph-theory, treewidth

> **Comments:**
> **username_1**: As i understand your conditions, Complete graph satisfies this condition and is not of bounded tree width.  
> **username_0**: @username_1 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.  
> **username_2**: 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., http://digitalarchive.maastrichtuniversity.nl/fedora/get/guid:e5729e4d-247c-431d-b1ce-db84ca580e53/ASSET1 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.  

---

## 0 answers

