1
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – Eric Tressler
    Jul 16, 2010 at 5:15
  • $\begingroup$ Could you give a hyperlink to the arxiv paper? $\endgroup$
    – Emil
    Jul 16, 2010 at 10:45
  • $\begingroup$ (I know how to get it. It will just make things easier for everyone.) $\endgroup$
    – Emil
    Jul 16, 2010 at 10:46
  • $\begingroup$ btw, d(G)=1 for Eric Tressler's example $\endgroup$
    – Yaroslav Bulatov
    Jul 16, 2010 at 22:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Eric Tressler
    Jul 18, 2010 at 0:50

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.