+\thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
+Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized per
+\<Insert> and \<Delete> and in time $\O(\log n/\log\log n)$ per \<Connected>
+in the worst case.
+
+\proof
+The direct cost of an~\<Insert> is $\O(\log n)$ for the operations on the ET-trees
+(by Theorem \ref{etthm}). We will also have the insertion pre-pay all level increases of the new
+edge. Since the levels never decrease, each edge can be brought a~level up at most
+$L=\lfloor\log n\rfloor$ times. Every increase costs $\O(\log n)$ on the ET-tree
+operations, so we pay $\O(\log^2 n)$ for all of them.
+
+A~\<Delete> costs $\O(\log^2 n)$ directly, as we might have to update all~$L$
+ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization of
+\<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
+increases.
+
+To bring the complexity of the operation \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
+we apply the trick from Example \ref{accel} and store~$F_0$ in a~ET-tree with $a=\max(\lfloor\log n\rfloor,2)$.
+This does not hurt the complexity of insertions and deletions, but allows for faster queries.
+\qed
+
+\rem
+An~$\Omega(\log n/\log\log n)$ lower bound for the amortized complexity of the dynamic connectivity
+problem has been proven by Henzinger and Fredman \cite{henzinger:lowerbounds} in the cell
+probe model with $\O(\log n)$-bit words. Thorup has answered by a~faster algorithm
+\cite{thorup:nearopt} that achieves $\O(\log n\log^3\log n)$ time per update and
+$\O(\log n/\log^{(3)} n)$ per query on a~RAM with $\O(\log n)$-bit words. (He claims
+that the algorithm runs on a~Pointer Machine, but it uses arithmetic operations,
+so it does not fit the definition of the PM we use. The algorithm only does not
+need direct indexing of arrays.) So far, it is not known how to extend this algorithm
+to fit our needs, so we omit the details.
+
+%--------------------------------------------------------------------------------
+
+\section{Dynamic spanning forests}\id{dynmstsect}%
+
+Let us turn our attention back to the dynamic MSF now.
+Most of the early algorithms for dynamic connectivity also imply $\O(n^\varepsilon)$
+algorithms for dynamic maintenance of the MSF. Henzinger and King \cite{henzinger:twoec,henzinger:randdyn}
+have generalized their randomized connectivity algorithm to maintain the MSF in $\O(\log^5 n)$ time per
+operation, or $\O(k\log^3 n)$ if only $k$ different values of edge weights are allowed. They have solved
+the decremental version of the problem first (which starts with a~given graph and only edge deletions
+are allowed) and then presented a~general reduction from the fully dynamic MSF to its decremental version.
+We will describe the algorithm of Holm, de Lichtenberg and Thorup \cite{holm:polylog}, who have followed
+the same path. They have modified their dynamic connectivity algorithm to solve the decremental MSF
+in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
+
+\paran{Decremental MSF}%
+Turning the algorithm from the previous section to the decremental MSF requires only two
+changes: First, we have to start with the forest~$F$ equal to the MSF of the initial
+graph. As we require to pay $\O(\log^2 n)$ for every insertion, we can use almost arbitrary
+MSF algorithm to find~$F$. Second, when we search for an~replacement edge, we need to pick
+the lightest possible choice. We will therefore use the weighted version of the ET-trees (Corollary \ref{wtet})
+and scan the lightest non-tree edge incident with the examined tree first. We must ensure
+that the lower levels cannot contain a~lighter replacement edge, but fortunately the
+light edges tend to ``bubble up'' in the hierarchy of levels. This can be formalized as
+the following invariant:
+
+{\narrower
+\def\iinv{{\bo I\the\itemcount~}}
+\numlist\iinv
+\itemcount=2
+\:On every cycle, the heaviest edge has the smallest level.
+\endlist
+}
+
+\>This immediately implies that we always select the right replacement edge:
+
+\lemma\id{msfrepl}%
+Let $F$~be the minimum spanning forest and $e$ any its edge. Then among all replacement
+edges for~$e$, the lightest one is at the maximum level.
+
+\proof
+Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle
+rule (Lemma \ref{redlemma}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
+In a~moment, we will show that the symmetric difference~$C$ of these two cycles is again a~cycle.
+This implies that if $f_1$ is heavier than~$f_2$, then $f_1$~is the heaviest edge on~$C$, so
+$\ell(f_1) \le \ell(f_2)$ by I3. Therefore the lightest of all replacement edges must have
+the maximum level.
+
+Why is~$C$ a~cycle:
+Let $F^a$ and~$F^b$ be the trees of~$F-e$ in which the endpoints of~$e$ lie, and for
+every edge~$g$ going between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints.
+We know that $C_i$ consists of the path $F[f_i^a,e^a]$, the edge~$e$, the path $F[e^b,f_i^b]$,
+and the edge~$f_i$. Thus~$C$ must contain the paths $F[f_1^a,f_2^a]$ and $F[f_1^b,f_2^b]$ and
+the edges $f_1$ and~$f_2$, which together form a~simple cycle.
+\qed
+
+We now have to make sure that the additional invariant is indeed observed:
+
+\lemma\id{ithree}%
+After every operation, the invariant I3 is satisfied.
+
+\proof
+When the structure is freshly initialized, I3 is obviously satisfied, as all edges
+are at level~0. Sole deletions of edges (both tree and non-tree) cannot violate I3, so we need
+to check only the replaces, in particular the place when an~edge~$e$ gets its level increased.
+
+For the violation to happen for the first time, $e$~must be the heaviest on
+some cycle~$C$, so by the Cycle rule, $e$~must be non-tree. The increase of
+$\ell(e)$ must therefore take place when~$e$ is considered as a~replacement
+edge incident with some tree~$T_1$ at level $\ell=\ell(e)$. We will pause the
+computation just before this increase and we will prove that all other edges
+of~$C$ already are at levels greater than~$\ell$, so the violation cannot occur.
+
+Let us first show this for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself
+already are at the higher levels as they were moved there at the very beginning of the
+search for the replacement edge. The other tree edges incident with~$T_1$ would have
+lower levels, which is impossible since the invariant would be already violated.
+Non-tree edges of~$C$ incident with~$T_1$ are lighter than~$e$, so they were already considered
+as~candidates for the replacement edge, because the algorithm always picks the lightest
+candidate first. Such edges therefore have been already moved a~level up.
+
+The case of edges of~$C$ that do not touch~$T_1$ is easy to handle: Such edges do not exist.
+If they did, at least one more edge of~$C$ besides~$e$ would have to connect~$T_1$ with the other
+trees of level~$\ell$. We already know that this could not be a~tree edge. If it were a~non-tree
+edge, it could not have level greater than~$\ell$ by~I1 nor smaller than~$\ell$ by~I3. Therefore
+it would be a~level~$\ell$ edge lighter than~$e$, and as such it would have been selected as the
+replacement edge before $e$~was.
+\qed
+
+We can conclude:
+
+\thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}
+When we start with a~graph on $n$~vertices with~$m$ edges and we perform a~sequence of
+edge deletions, the MSF can be initialized in time $\O((m+n)\cdot\log^2 n)$ and then
+updated in time $\O(\log^2 n)$ amortized per operation.
+
+\paran{Fully dynamic MSF}%
+The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox
+reduction whose properties are summarized in the following theorem:
+
+\thmn{MSF dynamization, Holm et al.~\cite{holm:polylog}}
+Suppose that we have a~decremental MSF algorithm with the following properties:
+\numlist\ndotted
+\:For any $a$,~$b$, it can be initialized on a~graph with~$a$ vertices and~$b$ edges.
+\:Then it executes an~arbitrary sequence of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
+\endlist
+\>Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
+with no edges, that performs $m$~insertions and deletions in amortized time:
+$$
+\O\left( \log^3 n + \sum_{i=1}^{\log m} \sum_{j=1}^i \; t(\min(n,2^j), 2^j) \right) \hbox{\quad per operation.}
+$$
+
+\proofsketch
+The reduction is very technical, but its essence is the following: We maintain a~logarithmic number
+of decremental structures $A_0,\ldots,A_{\lfloor\log n\rfloor}$ of exponentially increasing sizes. Every non-tree
+edge is contained in exactly one~$A_i$, tree edges can belong to multiple structures.
+
+When an~edge is inserted, we union it with some of the $A_i$'s, build a~new decremental structure
+and amortize the cost of the build over the insertions. Deletes of non-tree edges are trivial.
+Delete of a~non-tree edge is performed on all $A_i$'s containing it and the replacement edge is
+sought among the replacement edges found in these structures. The unused replacement edges then have
+to be reinserted back to the structure.
+
+The original reduction of Henzinger et al.~\cite{henzinger:twoec} handles these reinserts by a~mechanism of batch insertions
+supported by their decremental structure, which is not available in our case. Holm et al.~have
+replaced it by a~system of auxiliary edges inserted at various places in the structure.
+We refer to the article \cite{holm:polylog} for details.
+\qed
+
+\corn{Fully dynamic MSF}
+There is a~fully dynamic MSF algorithm that works in time $\O(\log^4 n)$ amortized
+per operation for graphs on $n$~vertices.
+
+\proof
+Apply the reduction from the previous theorem to the decremental algorithm we have
+developed. This results in an~algorithm of amortized complexity $\O(\log^4\max(m,n))$ where~$m$
+is the number of operations performed. This could exceed $\O(\log^4 n)$ if
+$m$~is very large, but we can rebuild the whole structure after $n^2$~operations,
+which brings $\log m$ down to $\O(\log n)$. The $\O(n^2\log^4 n)$ cost of the
+rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation.
+\qed
+
+\rem
+The limitation of MSF structures based on the Holm's algorithm for connectivity
+to only edge deletions seems to be unavoidable. The invariant I3 could be easily
+broken for many cycles at once whenever a~very light non-tree edge is inserted.
+We could try increasing the level of the newly inserted edge, but we would quite
+likely hit I1 before we managed to skip the levels of all the heaviest edges on the
+particular cycles.
+
+On the other hand, if we decided to drop I3, we would encounter different problems. The ET-trees can
+bring the lightest non-tree incident with the current tree~$T_1$, but the lightest replacement edge
+could also be located in the super-trees of~$T_1$ at the lower levels, which are too large to scan
+and both I1 and I2 prevent us from charging the time on increasing levels there.
+
+An~interesting special case in which insertions are possible is when all non-tree
+edges have the same weight. This leads to the following algorithm for dynamic MSF
+on~graphs with a~small set of allowed edge weights. It is based on an~idea similar
+to the $\O(k\log^3 n)$ algorithm of Henzinger and King \cite{henzinger:randdyn},
+but adapted to use the better results on dynamic connectivity we have at hand.
+
+\paran{Dynamic MSF with limited edge weights}%
+Let us assume for a~while that our graph has edges of only two different weights (let us say
+1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall
+the observation in \ref{multiweight} that the basic structural properties of
+the MST's from Section \ref{mstbasics} still hold.
+
+We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge
+weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm maintaining
+an~arbitrary spanning forest~$F_1$ of~$G_1$, which is obviously minimum. Then we add
+another instance~$\C_2$ to maintain a~spanning forest~$F_2$ of the graph $G_2\cup F_1$
+such that all edges of~$F_1$ are forced to be in~$F_2$. Obviously, $F_2$~is the
+MSF of the whole graph~$G$ --- if any edge of~$F_1$ were not contained in~$\msf(G)$,
+we could use the standard exchange argument to create an~even lighter spanning tree.\foot{This
+is of course the Blue lemma in action, but we have to be careful as we did not have proven it
+for graphs with multiple edges of the same weight.}
+
+When a~weight~2 edge is inserted to~$G$, we insert it to~$\C_2$ and it either enters~$F_2$
+or becomes a~non-tree edge. Similarly, deletion of a~weight~2 edge is a~pure deletion in~$\C_2$,
+because such edges can be replaced only by other weight~2 edges.
+
+Insertion of edges of weight~1 needs more attention: We insert the edge to~$\C_1$. If~$F_1$
+stays unchanged, we are done. If the new edge enters~$F_1$, we use Sleator-Tarjan trees
+kept for~$F_2$ to check if the new edge covers some tree edge of weight~2. If this is not
+the case, we insert the new edge to~$\C_2$ and hence also to~$F_2$ and we are done.
+Otherwise we exchange one of the covered weight~2 edges~$f$ for~$e$ in~$\C_2$. We note
+that~$e$ can inherit the level of~$f$ and $f$~can become a~non-tree edge without
+changing its level. This adjustment can be performed in time $\O(\log^2 n)$, including
+paying for the future level increases of the new edge.
+
+Deletion of weight~1 edges is once more straightforward. We delete the edge from~$\C_1$.
+If it has no replacement, we delete it from~$\C_2$ as well. If it has a~replacement,
+we delete the edge from~$\C_2$ and insert the replacement on its place as described
+above. We observe than this pair of operations causes an~insertion, deletion or
+a~replacement in~$\C_2$.
+
+This way, we can handle every insertion and deletion in time $\O(\log^2 n)$ amortized.
+This construction can be iterated in an~obvious way: if we have $k$~distinct edge weights,
+we build $k$~connectivity structures $\C_1,\ldots,\C_k$. The structure~$\C_i$ contains edges of
+weight~$i$ together with the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy:
+
+\thmn{MSF with limited edge weights}
+There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized
+per operation for graphs on $n$~vertices with only $k$~distinct edge weights allowed.
+
+\proof
+A~change in the graph~$G$ involving an~edge of weight~$w$ causes a~change in~$\C_w$,
+which can propagate to~$\C_{w+1}$ and so on, possibly up to~$\C_k$. In each~$\C_i$,
+we spend time $\O(\log^2 n)$ by updating the connectivity structure according to
+Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan trees
+by Theorem \ref{sletar}.
+\qed