4
$\begingroup$

Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.

Now consider the following random process. First sample a uniformly random spanning tree of $G$ and then pick an edge from this spanning tree uniformly at random. Our process returns the edge.

If I want to sample many edges from $G$ from the probability distribution implied by this process, is there a more efficient (in terms of computational complexity) method than sampling a new random spanning tree each time?

$\endgroup$
4
$\begingroup$

While the other answer is correct, it requires the computation of $|E| + 1$ many determinants. There is a faster route when $|E|$ is large. The first thing to note is Kirchoff's theorem which states that if $T$ is a uniform spanning tree then $$P(e \in T) = \mathscr{R}(e_- \leftrightarrow e_+)$$ where $e = \{e_-, e_+\}$ and $\mathscr{R}(a \leftrightarrow b)$ is the effective resistance between $a$ and $b$ when each edge is given resistance $1$. This implies that the probability an edge is sampled in your process is $$\mathscr{R}(e_- \leftrightarrow e_+)/(|V| - 1).$$

Thus we only need to compute the effective resistance.

If we let $L$ denote the graph Laplacian and $L^+$ to be its Moore-Penrose pseudoinverse, then

$$\mathscr{R}(a \leftrightarrow b) = (L^+)_{aa} + (L^+)_{bb} - 2 (L^+)_{ab}. $$

(See this master's thesis for some nice discussion and references.)

Thus, the only computational overhead for computing the marginals is computing a single psuedoinverse. Depending on how large $|E|$ is, this may be faster than computing $|E|$ many determinants.

EDIT: some discussion on complexity

The Pseudoinverse of an $n \times n$ matrix can be done in $O(n^3)$ time. So computing $L^+$ takes $O(|V|^3)$ time. We have to compute this for $|E|$ many edges, so the above computes all marginals in $O(|E| |V|^3)$ time. Conversely, a determinant can be done in, say, $O(n^{2.3})$ time. So the other answer has complexity $O(|E|^2 |V|^{2.3}).$ Since $G$ is connected, $|E| \geq |V|-1$ and so this algorithm is always faster (asymptotically, at least).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is great. I wonder if this is as fast as it gets. $\endgroup$ – donald Aug 5 at 16:12
  • 1
    $\begingroup$ A correction on the complexity: (i) the pseudoinverse can be calculated in matrix multiplication time (see e.g. here), which is $O(n^{2.373})$, (ii) you only have to calculate it once - after that you can just read off the eff.resistances in constant time. This gives a total time complexity equal to the matrix multiplication time, $O(n^{2.373})$. $\endgroup$ – smapers Aug 12 at 9:35
3
$\begingroup$

Let $\tau(G)$ denote the number of spanning trees in $G$, and let $G \bullet vw$ denote edge contraction: it is the multigraph in which adjacent vertices $v$ and $w$ are replaced by a single vertex $x$, and all edges incident to either $v$ or $w$ are changed to be adjacent to $x$.

The spanning trees of $G$ containing edge $vw$ are in bijection with the spanning trees of $G \bullet vw$, and so the probability that your process will return $vw$ is $$\frac{\tau(G \bullet vw)}{\tau(G)} \cdot \frac1{|V(G)|-1}.$$ We can efficiently compute $\tau(H)$ for any multigraph graph $H$ using Kirchhoff's matrix tree theorem.

(Rather than dealing with $G\bullet vw$, we could also count the spanning trees containing $vw$ as $\tau(G) - \tau(G-vw)$, but that's slightly less efficient, because the determinants are one bigger.)

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Approximately sampling according to the effective resistances is done in the sparsification algorithm of Spielman and Srivastava. See Theorem 2 of this paper. The complexity has a one-off cost of $\tilde{O}(m)$, and then cost $\tilde{O}(1)$ per sample.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.