# Talk:Tree decomposition

WikiProject Mathematics (Rated B-class, Mid-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 B Class
 Mid Importance
Field:  Discrete mathematics
WikiProject Computer science (Rated B-class, Mid-importance)
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B  This article has been rated as B-Class on the project's quality scale.
Mid  This article has been rated as Mid-importance on the project's importance scale.

## Relation to junction trees

What's the relation between this and Junction tree or join tree? Are they the same? Took 03:13, 20 March 2007 (UTC)

I think they are the same, and merged them. There was a very vague handwavy description of how to find a tree decomposition in the junction tree article, which I didn't consider worth saving, but there's plenty more that could be said in this article on the topic of decomposition algorithms. This should link in to graph separators, as well. —David Eppstein 16:30, 3 November 2007 (UTC)
I don't believe that they are the same- I believe a junction tree is a specific type of join tree, which is optimised for the calculation of bayesian inference. —Preceding unsigned comment added by 129.215.90.27 (talk) 09:30, 21 October 2008 (UTC)
I agree - they are not the same. The junction tree is one particular tree decomposition, it is the one which maximizes the weight of the tree. The weight of tree is the sum of its edge weights. The weight of an edge is the number of nodes shared by the two cliques it connects. 115.129.16.201 (talk) 14:41, 27 June 2009 (UTC) Dmitry Kamenetsky

## The recursion for Independent Set

I have a suggestion for a different formulation of A in the recursion for Independent Set. Let ${\displaystyle C(i)}$ be the direct children of node ${\displaystyle i}$ in the tree decomposition. (Since we have chosen a root for the tree this is ok.)

${\displaystyle A(S,i)=|S|+\sum _{j\in C(i)}\left((\max _{S'\subset X_{j} \atop {S\cap X_{j}=S'\cap X_{i} \atop S\cup S'{\text{independent set}}}}A(S',j))-|S\cap X_{j}|\right)}$

This way we dont need the extra function B. What do you think? Dag Hovland (talk) 10:37, 7 December 2007 (UTC)

## Books?

Could anyone provide a reference for a really good book covering this and similar (algorithms and graph theory) topics? —Preceding unsigned comment added by 81.110.32.149 (talk) 19:42, 8 January 2008 (UTC)

## Treewidth of trees

The article claims "A graph has treewidth 1 if and only if it is a tree", which is not true: forests consisting of multiple trees have treewidth at most 1, too, and trees (forests) without edges have treewidth 0. I'm not sure how to best correct this though, as I'm reluctant to change the section from "treewidth of trees" to "treewidth of forests".85.178.88.61 (talk) 17:09, 31 July 2008 (UTC)

I changed it to talk about connected graphs. —David Eppstein (talk) 00:52, 1 August 2008 (UTC)

## junction tree

in the article, the link "junction tree" actually links to junction tree algorithm. junction tree algorithm again has a link to junction tree. This one goes to junction tree. But junction tree is a redirect back to this here article. So, what a junction tree is remains unclear. --91.0.23.173 (talk) 02:01, 15 January 2010 (UTC)

I think it's a tree decomposition of the moral graph of the representation of a Bayesian network as a directed acyclic graph, but I'm not certain enough to make that change here. —David Eppstein (talk) 02:06, 15 January 2010 (UTC)
Following [Lauritzen], "Junction Tree" is a tree-decomposition into complete parts (ie, each bag is a clique). Such decomposition is possible iff graph is triangulated. For relevance to inference -- in an undirected graphical model, conditioning on a separator of the graph makes separated parts of probabilistic network independent, so inference can proceed recursively using tree decomposition, this algorithm is called the junction tree algorithm . Conditioning on separators in Bayesian networks does not always create independent subproblems, but every Bayesian network can be converted to an undirected graphical model (this involves moralizing the graph). Yaroslav Bulatov (talk) 23:51, 6 November 2010 (UTC)