BTW, tree decomposition is a generalization of dynamic programming. In a general structured problem you may not have a nice table recursion like in edit-distanc

BTW, tree decomposition is a generalization of dynamic programming. In a general structured problem you may not have a nice table recursion like in edit-distance example, and tree decomposition is what you get when you abstract away from tables. When problem structure comes from the real world, like with probabilistic networks, computers are much better at finding a good recursion than humans. Here are some pictures to illustrate tree decomposition http://yaroslavvb.blogspot.com/2011/02/generalized-distributive-law.html http://yaroslavvb.blogspot.com/2011/02/generalized-distribut...