# Linking and Cutting Spanning Trees
## 3 Main Idea  
To generate a uniform spanning tree, start by generating an arbitrary spanning tree \(A\). One way to obtain this tree is to compute a depth first search in \(G\), in which case the necessary time is \(O(V+E)\). In general, we want the mixing time of our chain to be much smaller than \(O(E)\), especially for dense graphs. This initial tree is only generated once, and subsequent trees are obtained by the randomizing process. To randomize \(A\), repeat the next process several times. Choose an edge \((u,v)\) from \(E\) uniformly at random, and consider the set \(A\cup\{(u,v)\}\). If \((u,v)\) already belongs to \(A\) the process stops, otherwise \(A\cup\{(u,v)\}\) contains a cycle \(C\). To complete the process, choose an edge \((u^{\prime},v^{\prime})\) uniformly from \(C\setminus\{(u,v)\}\) and remove it. Hence, at each step the set \(A\) is transformed into the set \((A\cup\{(u,v)\})\setminus\{(u^{\prime},v^{\prime})\}\). An illustration of this process is shown in Figure 3.  
Figure 3: Edge-swap procedure. Inserting the edge \((u,v)\) into the initial tree \(A\) generates a cycle \(C\). The edge \((u^{\prime},v^{\prime})\) is removed from \(C\). Figure 2: A star graph on \(K_{4}\), centered at 1. This edge-swapping process can be adequately modeled by a Markov chain, where the states corresponds to different spanning trees and the transitions among states correspond to the process we have just described. In Section 4.1 we study the ergodic properties of this chain. For now let us focus on which data structures can be used to compute the transition procedure efficiently. A simple solution to this problem would be to compute a depth first search (DFS) on \(A\), starting at \(u\) and terminating whenever \(v\) is reached. This allows us to identify \(C\) in \(O(V)\) time. Recall that \(A\) contains exactly \(V-1\) elements. The edge \((u^{\prime},v^{\prime})\) can then be easily removed. Besides \(G\) the elements of \(A\) also need to be represented with the adjacency list data structure. For our purposes, this approach is inefficient. This computation is central to our algorithm and its complexity becomes a factor in the overall performance. Hence, we will now explain how to perform this operation in only \(O(\log V)\) amortized time with the link-cut tree data structure. The link-cut tree (LCT) is a data structure that can used to represent a forest of rooted trees. The representation is dynamic so that edges can be removed and added. Whenever an edge is removed, the original tree is cut in two. Adding an edge between two trees links them. This structure was proposed by [PERSON] and [PERSON] and [PERSON] (2000). Both the link and cut operations can be computed in \(O(\log V)\) amortized time. The LCT can only represent trees; therefore the edge swap procedure must first cut the edge \((u^{\prime},v^{\prime})\) and afterwards insert the edge \((u,v)\) with the Link operation. The randomizing process needs to identify \(C\) and select \((u^{\prime},v^{\prime})\) from it. The LCT can also compute this process in \(O(\log V)\) amortized time. The LCT works by partitioning the represented tree into disjoint paths. Each path is stored in an auxiliary data structure, so that any of its edges can be accessed efficiently in \(O(\log V)\) amortized time. To compute this process we force the path \(D=C\setminus\{(u,v)\}\) to become a disjoint path. This means that \(D\) will be completely stored in one auxiliary data structure. Hence, it is possible to efficiently select an edge from it. Moreover the size of \(D\) can also be computed efficiently. The exact process, to force \(D\) into an auxiliary structure, is to make \(u\) the root of the represented tree and then access \(v\). Algorithm 1 shows the pseudo-code of the edge-swapping procedure. We can confirm, by inspection, that this process can be computed in the \(O(\log V)\) amortized time bound that is crucial for our main result.