Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of self avoiding walks on $G$ passing through nodes $u$ and $v$ for all pairs of nodes $(u,v)$. For a single pair $(u,v)$, one approach is dynamic programming on a tree decomposition of the graph constrained to have a bag containing both $u$ and $v$. For all pairs of nodes, one may need to consider several tree decompositions, so that every pair of vertices is contained in some bag of some decomposition. The interesting question is how to come up with a such a set of tree decompositions so that they the overall problem complexity is kept low. Has this kind of problem been studied?

Some other problems where "tree decomposition ensemble" might be useful

  • all pairwise marginals in a graphical model
  • two-point correlation function for Ising/Potts/hardcore models on finite graph
  • Hessian of $f:\mathbb{R}^{|V|}->\mathbb{R}$ where $f$ is some function whose computation relies on tree decomposition of $G$. For instance, $f$ could be multivariate Potts polynomial of $G$, some general labeled graph polynomial or partition function of Gibbs distribution on $G$
  • computing how some FP+C definable graph invariant is affected by deletion of any pair of vertices
  • $\begingroup$ for any particular pair, you can get the desired decomposition merely by adding an edge between u and v and then running a tree decomposition, right ? $\endgroup$ Nov 10, 2010 at 18:14
  • $\begingroup$ yes ;;;;;;;;;;; $\endgroup$ Nov 10, 2010 at 18:38
  • $\begingroup$ One approach might be to add several edges at a time, as long as that doesn't increase tree-width beyond adding just one edge $\endgroup$ Nov 10, 2010 at 19:08

1 Answer 1


I would simply do as follows:

Start with a tree decomposition $T$ of $G$. Each time you would like to compute the number of self avoiding walks on $G$ passing through $u$ and some other node, do dynamic programming on the tree decomposition $T'$ obtained from $T$ by adding $u$ to each bag of the tree decomposition. The width of $T'$ is at most the width of $T$ plus one, and you cannot hope for anything better in general.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.