Fix some finite graph $ G = (V, E)$ , and some vertex $ x$ .
Suppose I generate a random subtree of $ G$ of size $ N$ , containing $ x$ , as follows:
 Let $ T_0 = \{ x \}$ .

For $ 0 < n \leqslant N$
i. Let $ B_n$ be the set of $ y \in V$ such that $ y \notin V(T_{n1})$ , and such that $ (x, y) \in E \text{ for exactly one } x \in V(T_{n1})$ .
ii. Form $ T_n$ by
 Selecting some $ y_n \in B_n$ with probability $ q_n (y_n  T_{n1} )$ ,
 Adding it to $ T_{n1}$ , and
 Adding the edge between $ y$ and its neighbour in $ V (T_{n1})$ .

Return $ T_N$ .
Suppose also that $ q_n (y_n  T_{n1} )$ can be computed easily for all $ (T_{n1}, y_n)$ . I am interested in efficiently calculating the marginal probability of generating the tree $ T_N$ , given that I began growing it at $ T_0 = \{ x \}$ , i.e.
$ $ P(T_N  T_0 = \{ x \}) = \sum_{y_1, \cdots, y_N} \prod_{n = 1}^N q_n (y_n  T_{n1} ).$ $
My question is essentially whether I should expect to be able to find an efficient (i.e. polynomialtime) algorithm for this, and if so, what it might be.
Some thoughts:

Naively, the sum has exponentiallymany terms, which precludes trying to evaluate the sum directly.

On the other hand, this problem is also highlystructured (trees, recursion, etc.), which might suggest that some sort of dynamic programming approach would be feasible. I’m not sure of exactly how to approach this.

Relatedly, I know how to calculate unbiased, nonnegative estimators of $ P(T_N  T_0 = \{ x \})$ , which have reasonable variance properties, by using techniques from Sequential Monte Carlo / particle filtering. This suggests that the problem is at least possible to approximate well in a reasonable amount of time.