Ensemble of tree decompositions for all-pairs problem 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|}-&gt;\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
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&#39;$ obtained from $T$ by adding $u$ to each bag of the tree decomposition. The width of $T&#39;$ is at most the width of $T$ plus one, and you cannot hope for anything better in general.