<p>I would simply do as follows:</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-10T11:13:45.007Z
2011-01-10T11:13:45.007Z
Serge Gaspers
<p>Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of <a href="http://en.wikipedia.org/wiki/Self-avoiding_walk" rel="nofollow">self avoiding walks</a> 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  <a href="http://en.wikipedia.org/wiki/Tree_decomposition" rel="nofollow">tree decomposition</a> 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?</p>

<p>Some other problems where "tree decomposition ensemble" might be useful </p>

<ul>
<li>all pairwise marginals in a graphical model</li>
<li>two-point correlation function for Ising/Potts/hardcore models on finite graph</li>
<li>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.159.1249" rel="nofollow">labeled</a> graph polynomial or partition function of Gibbs distribution on $G$</li>
<li>computing how some FP+C definable graph invariant is affected by deletion of any pair of vertices</li>
</ul>

CC BY-SA 2.5
2010-11-10T18:14:58.950Z
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
CC BY-SA 2.5
2010-11-10T18:38:43.030Z
yes ;;;;;;;;;;;
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-10T19:08:23.147Z
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
<graph-theory><reference-request><co.combinatorics><treewidth><statistical-physics>
Ensemble of tree decompositions for all-pairs problem
Yaroslav Bulatov
# Ensemble of tree decompositions for all-pairs problem

(Asked by: username_0 on 2010-11-07)

Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of [self avoiding walks](http://en.wikipedia.org/wiki/Self-avoiding_walk) 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](http://en.wikipedia.org/wiki/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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.159.1249) 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

**Tags:** graph-theory, reference-request, co.combinatorics, treewidth, statistical-physics
> **Comments:**
> **username_1**: 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 ?  
> **username_0**: yes ;;;;;;;;;;;  
> **username_0**: 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  

---

## 1 answers

### Answer by username_2 on 2011-01-10. Score: 3 | Accepted answer

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.


---

