

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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
share|cite|improve this question
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 ? – Suresh Venkat Nov 10 '10 at 18:14
yes ;;;;;;;;;;; – Yaroslav Bulatov Nov 10 '10 at 18:38
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 – Yaroslav Bulatov Nov 10 '10 at 19:08
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


