Talk:Tree decomposition

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 $C(i)$ be the direct children of node $i$ in the tree decomposition. (Since we have chosen a root for the tree this is ok.)

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

Wording of lead

The wording of the intro to this article could be improved: I just read it and yet cannot figure out what a Tree Decomposition IS. The intro says "a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph." but does not say what the mapping IS. Only the purpose the mapping. Ok, ok, I get it, it's used to speed up things. But what IS it? What IS the mapping? Then if I read the definition section, it says "Intuitively, a tree decomposition represents the vertices of the given graph as subtrees of a tree, in such a way that vertices are adjacent only when the corresponding subtrees intersect." But this is confusing in the following ways: (1) I do not know what it means to represent vertices of a graph as subtrees. Vertices are vertices; a tree has vertices AND edges. So this sentence does not type-check for me. Do you really mean a subgraph of this graph is represented as subtrees? (2) It is getting ambiguous when specifying "vertices are adjacent" ... vertices of WHAT are adjacent? The original graph? The tree decomposition? This whole introduction really needs to be rewritten... I cannot understand it, and I'm a PhD in computer science. --Toomim (talk) 22:23, 9 February 2012 (UTC)

Agree, the wording is still less than optimal. [ɯ:] (talk) 13:28, 5 February 2013 (UTC)

Nice tree decompositions

When I was first learning dynamic programming on tree decompositions I found the Independent Set example currently on the Tree Decomposition page (with a recurrence for both A and B) really quite dense and confusing. On the other hand, there are slides on the internet in which Vertex Cover is computed using "nice" tree decompositions (i.e. with leaf, forget, introduce, join nodes) and a convincing sketch proof of correctness fits into a few lines. Of course you need to leverage the known result that nice tree decompositions do not inflate the width of the decomposition, but I'd consider this a small price to pay for explaining to a wider audience the power of DP on tree decompositions. So I guess the question is: is it a good idea to introduce nice tree decompositions and give a (sketch) proof of why the DP is correct?Steven.kelk (talk) 11:48, 18 August 2015 (UTC)