Let p=(v_{1},…,v_{n}) 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 v_{n} and ends at v_{i} without visiting any other vertices in p. Let d(G) be max_{p} 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

2more comments