Marginal Probability of Generating a Tree

Fix some finite graph $$G = (V, E)$$, and some vertex $$x$$.

Suppose I generate a random sub-tree of $$G$$ of size $$N$$, containing $$x$$, as follows:

1. Let $$T_0 = \{ x \}$$.
2. For $$0 < n \leqslant N$$

i. Let $$B_n$$ be the set of neighbors of $$T_{n-1}$$ outside of $$T_{n-1}$$.

ii. Form $$T_n$$ by

• Sample a pair $$(x_n, y_n) \in E(G) \cap \left( V (T_{n-1}) \times B_n \right)$$, with probability $$q_n (x_n, y_n | T_{n-1} )$$,
• Add $$y_n$$ to $$V(T_{n-1})$$, and add $$(x_n, y_n)$$ to $$E (T_{n-1})$$.
3. Return $$T_N$$.

Suppose also that $$q_n ( x_n, y_n | T_{n-1} )$$ can be computed easily for all $$(T_{n-1}, x_n, y_n)$$. I am interested in efficiently and exactly 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_{x_{1:N}, y_{1:N}} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

My question is essentially whether I should expect to be able to find an efficient (i.e. polynomial-time) algorithm for this, and if so, what it might be.

Some thoughts:

• Naively, the sum has exponentially-many terms, which precludes trying to evaluate the sum directly.

• On the other hand, this problem is also highly-structured (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, non-negative 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.

• $B_n$ could be empty, depending on $G$ and the previously chosen vertices. Perhaps you mean to say that $B_n$ is the set of neighbors of $T_{n-1}$ outside $T_{n-1}$? Jun 2 '20 at 13:22
• @Ariel - that's a good point. I have been tacitly assuming that $B_n$ will always be non-empty for the $N$ I choose (in my application, this is the case), so I will make that more explicit. Re: your suggestion, I'll reformulate things slightly, as your comment has helped me to realise that my problem can be posed slightly more generally than I had thought.
– πr8
Jun 2 '20 at 14:29

No. If $$q(x_n,y_n|T_{n-1})$$ is arbitrary -- there can be an arbitrary dependence on $$T_{n-1}$$ -- then this requires exponential time.

Consider a tree $$T_N$$ that has a single root node, $$N-1$$ leaves, and an edge from the root to each leaf. There are $$2^N$$ subtrees of $$T_N$$, and in particular, there are $$2^N$$ possible values of $$T_n$$ that can occur in the expression

$$\sum_{x, y} \prod_{n = 1}^N q_n (x_n, y_n | T_{n-1} ).$$

One can use a simple adversary argument to prove that evaluating this expression requires exponential time. Suppose that we evaluate $$q_n(x_n,x_n|T_{n-1})$$ by querying an oracle with $$x_n,y_n,T_{n-1}$$. Suppose there is a single tree $$T$$ that is never queried to the oracle as any $$T_{n-1}$$. Choose all of the $$q_n(\cdots)$$ values to be strictly positive. Then since $$q_n(x_n,y_n|T)$$ wasn't queried during execution, we can choose it after observing the output of the algorithm; but by varying it, we can choose a value that makes the algorithm's output wrong (in particular, the value of the expression depends on $$q_n(x_n,y_n|T)$$ but the algorithm's output doesn't depend on $$q_n(x_n,y_n|T)$$, so the algorithm's output cannot correct). We have proven that, to produce the correct output, any correct algorithm must query the oracle for all $$2^N$$ possible subtrees of $$T_N$$. It takes at least $$O(1)$$ time to query an oracle.

In conclusion, this argument proves that any correct algorithm for computing this expression must take $$\Omega(2^N)$$ time.

I don't know whether it can always be done in $$O(2^N)$$ time, or whether perhaps $$O(N!)$$ time might be required.

• Hi - where have I written $q(x_n, y_n | T_n)$? I agree that it should be $q(x_n, y_n | T_{n-1})$ throughout. Re: the main comment - I think that there are generally much fewer than $N!$ valid orderings, as each time an edge is added, it must be added to an existing edge. For example, if the final tree is a chain graph on $\{ 1, 2, \ldots, N \}$, and one began growing the tree from $\{ k \}$, then there are ${ N \choose k}$ ways in which the vertices could be added. Admittedly, this may still be exponentially-large in $N$ (e.g. take $k \sim \alpha n$).
– πr8
Jun 3 '20 at 9:11
• One approach which I'm considering is to show that the set of possible 'partial trees' $T_n$ at each $n \in \{ 1, \ldots, N \}$ which extend $\{ x \}$ and which can be extended to $T_N$, is not too large (e.g. at most polynomial in $N$). If there is a 'final tree' $T_N$ and an 'initial vertex' $x$ for which this is not the case, it would show that this is not possible in general.
– πr8
Jun 3 '20 at 9:18
• Consider $T_{N+1}$ which consists of $x$ and $N$ vertices adjacent to $x$ (a tree of height 1, where $x$ is the root and has $N$ children). There are $N!$ possible constructions (where a construction is a permutation of the edges in the tree) that produces $T_{N+1}$ (any edge can be chosen at any step). While this is a good intuition, this is definitely not a proof. Jun 3 '20 at 10:06
• A complete binary tree rooted at $x$ with $N$ additional vertices also admits to $N!$ possible constructions (at the first step you have two choices, and each step the number of candidates increases by one). Jun 3 '20 at 17:41
• @Ariel, great example! See revised answer for an argument that this problem requires exponential time in the worst case.
– D.W.
Jun 3 '20 at 18:06