

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

Let p=(v1,…,vn) be a self-avoiding walk in a graph G. Let d(p) be the number of unique i, 1≤i<n such that there's a self-avoiding walk q that starts at vn and ends at vi without visiting any other vertices in p. Let d(G) be maxp d(p) with maximum taken over all self-avoiding walks in G. Is d(G) related to treewidth of G?

Motivation: arXiv:math/0701494 gives a way to represent marginal probability of a node on an arbitrary graph (ie, the probability of that node taking a particular color when we randomly pick a proper coloring of G) as the marginal probability of the root of a self-avoiding walk tree built from this graph. Finding marginal probability in this representation seems to scale exponentially in d(G), whereas finding marginal in original representation (junction tree algorithm), scales exponentially in treewidth of G.

This relates to the complexity of counting the number of colorings in a graph, because there's a computationally efficient way to get the number of colorings from marginals (sequential cavity method), so if d(G) grew slower than treewidth(G) for some family of graphs, this would give an algorithm for counting colorings that's faster than the tree-decomposition based one

share|cite|improve this question
Consider $N$ copies of $C_3$ (picture equilateral triangles with one side horizontal) connected in a chain, the right base vertex of one triangle connected to the left base vertex of the next. This graph has $2N+1$ vertices and treewidth 2. Taking the horizontal path to be our self-avoiding walk, this path has length $N+1$ and $2^N$ ways to get from the leftmost vertex to the rightmost (not even counting the other paths we care about) -- at each point, I can walk right, or go up the triangle and back down. That's not an answer, but it's evidence. Of something. – Eric Tressler Jul 16 '10 at 5:15
Could you give a hyperlink to the arxiv paper? – Emil Jul 16 '10 at 10:45
(I know how to get it. It will just make things easier for everyone.) – Emil Jul 16 '10 at 10:46
btw, d(G)=1 for Eric Tressler's example – Yaroslav Bulatov Jul 16 '10 at 22:44
You're right, Yaroslav. I neglected the condition "without visiting any other vertices in $p$". My example can be easily altered, though, to give a graph with treewidth 4 and $d(G)$ exponential in $|V|$ -- add a second copy of $P_{N+1}$ beneath the first path, and connect each new vertex to the vertex above it. – Eric Tressler Jul 18 '10 at 0:50
up vote 1 down vote accepted

If a graph has bounded treewidth, it has $O(n)$ edges. And if it has $O(n)$ edges, it has $2^{O(n)}$ self-avoiding walks, since a self-avoiding walk can be specified as a set of edges. This is in contrast with arbitrary graphs where the number of self-avoiding walks can be exponential in $n\log n$. But it's not really a relation to treewidth since the same thing holds for any sparse graph.

share|cite|improve this answer

Your Answer


