Larger cover letters.

[saga.git] / dyn.tex

diff --git a/dyn.tex b/dyn.tex
index 943231884c60976d8e78f875dd1d575772dbc9e3..f07103ac08cc19f4d596c73cca1c8d1aee0545b5 100644 (file)
--- a/dyn.tex
+++ b/dyn.tex
@@ -68,8 +68,8 @@ therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the followi
 Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
 and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
 
 Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
 and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
 

-Correctness of the former case follows immediately from the Theorem on Minimality by order
-(\ref{mstthm}), because any $F'$-light would be also $F$-light, which is impossible as $F$~was
+Correctness of the former case follows immediately from the Minimality Theorem (\ref{mstthm}),
+because any $F'$-light would be also $F$-light, which is impossible as $F$~was

 minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
 on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
 (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$
 minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
 on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
 (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$


@@ -185,7 +185,7 @@ from the Link-Cut tree, knowing that there is no edge to replace it). The hard p
 is the search for replacement edges after an~edge belonging to the MSF is deleted.
 
 This very problem also has to be solved by algorithms for fully dynamic connectivity,
 is the search for replacement edges after an~edge belonging to the MSF is deleted.
 
 This very problem also has to be solved by algorithms for fully dynamic connectivity,

-we will take a~look on them first.
+we will take a~look at them first.

 
 %--------------------------------------------------------------------------------
 
 
 %--------------------------------------------------------------------------------
 


@@ -225,7 +225,7 @@ $AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two sequences $AuC$ and $vBv$.
 If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence
 transforms from $AuvuC$ to $AuC$ and $v$~alone.
 
 If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence
 transforms from $AuvuC$ to $AuC$ and $v$~alone.
 

-\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes the sequence from $vAwBwCv$ to $wBwCvAw$.
+\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes its ET-sequence from $vAwBwCv$ to $wBwCvAw$.

 If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
 the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
 
 If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$,
 the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$.
 


@@ -401,39 +401,43 @@ We will maintain the following \em{invariants:}
 {\narrower
 \def\iinv{{\bo I\the\itemcount~}}
 \numlist\iinv
 {\narrower
 \def\iinv{{\bo I\the\itemcount~}}
 \numlist\iinv

-\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. In other words,
-if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.
-\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices.
-This implies that all~$F_i$ for $i>L$ are empty.
+\:$F$~is the maximum spanning forest of~$G$ with respect to the levels. (In other words,
+if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$.)
+\:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices each.
+(This implies that it does not make sense to define~$F_i$ for $i>L$, because it would be empty
+anyway.)

 \endlist
 }
 
 At the beginning, the graph contains no edges, so both invariants are trivially
 \endlist
 }
 
 At the beginning, the graph contains no edges, so both invariants are trivially

-satistifed. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.
+satisfied. Newly inserted edges can enter level~0, which cannot break I1 nor~I2.

 
 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
 smaller one. We will try to find the replacement edge of the highest possible
 
 When we delete a~tree edge at level~$\ell$, we split a~tree~$T$ of~$F_\ell$ to two
 trees $T_1$ and~$T_2$. Without loss of generality, let us assume that $T_1$ is the
 smaller one. We will try to find the replacement edge of the highest possible

-level that connects them back. From I1, we know that such an~edge cannot belong to
-level greater than~$\ell$, so we start looking for it at level~$\ell$. According
+level that connects the spanning tree back. From I1, we know that such an~edge cannot belong to
+a~level greater than~$\ell$, so we start looking for it at level~$\ell$. According

 to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
 at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can increase the levels
 of all edges of~$T_1$ without violating either invariant.
 
 to~I2, the tree~$T$ had at most $\lfloor n/2^\ell\rfloor$ vertices, so $T_1$ has
 at most $\lfloor n/2^{\ell+1} \rfloor$ of them. Thus we can increase the levels
 of all edges of~$T_1$ without violating either invariant.
 

-We now start enumerating the non-tree edges incident with~$T_1$. For each such edge,
-we test whether its other endpoint lies in~$T_2$. If it does, we have found the replacement
-edge and we insert it to~$F_\ell$. Otherwise we move the edge one level up. (This will
-be the gist of our amortization argument: We can charge most of the work on level
+We now start enumerating the non-tree edges incident with~$T_1$. Each such edge
+is either local to~$T_1$ or it joins $T_1$ with~$T_2$. We will therefore check each edge
+whether its other endpoint lies in~$T_2$ and if it does, we have found the replacement
+edge, so we insert it to~$F_\ell$ and stop. Otherwise we move the edge one level up. (This
+will be the grist for the mill of our amortization argument: We can charge most of the work at level

 increases and we know that the level of each edge can reach at most~$L$.)
 
 If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next
 increases and we know that the level of each edge can reach at most~$L$.)
 
 If the non-tree edges at level~$\ell$ are exhausted, we try the same in the next

-lower level and so on. If there is no replacement edge on level~0, the tree~$T$
+lower level and so on. If there is no replacement edge at level~0, the tree~$T$

 remains disconnected.
 
 \impl
 remains disconnected.
 
 \impl

-We will use a~single ET-tree with~$a$ set to~2 for each level. For the $i$-th level, the ET-tree
-${\cal E}_i$ will represent the forest~$F_i$ and the non-tree edges of
-level~$i$ will be attached to its vertices.
+For each level, we will use a~separate ET-tree ${\cal E}_\ell$ with~$a$ set to~2,
+which will represent the forest~$F_i$ and the non-tree edges at that particular level.
+Besides operations on the non-tree edges, we also need to find the tree edges of level~$\ell$
+when we want to bring them one level up. This can be accomplished either by modifying the ET-trees
+to attach two lists of edges attached to vertices instead of one, or by using a~second ET-tree.

 
 \algn{Insertion of an~edge}
 \algo
 
 \algn{Insertion of an~edge}
 \algo


@@ -452,33 +456,39 @@ level~$i$ will be attached to its vertices.
 \:If $uv$ is a~non-tree edge:
 \::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$.
 \:Otherwise:
 \:If $uv$ is a~non-tree edge:
 \::Remove $uv$ from the lists of non-tree edges at both $u$ and~$v$ in~${\cal E}_{\ell}$.
 \:Otherwise:

-\::Remove $uv$ from~$F_\ell$.
-\::Call $\<Replace>(uv,\ell)$.
+\::Remove $uv$ from~$F_\ell$ and hence also from $F_0,\ldots,F_{\ell-1}$.
+\::Call $\<Replace>(uv,\ell)$ to get the replacement edge~$f$.
+\::Insert $f$ to~$F_0,\ldots,F_{\ell(f)}$.

 \endalgo
 
 \endalgo
 

-\algn{$\<Replace>(uv,i)$ -- Search for an~replacement edge for~$uv$ at level~$i$}
+\algn{$\<Replace>(uv,i)$ -- Search for replacement for edge~$uv$ at level~$i$}

 \algo
 \algo

+\algin An~edge~$uv$ to replace and a~level~$i$ such that there is no replacement
+at levels greater than~$i$.

 \:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively.
 \:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$.
 \:Let $T_1$ and~$T_2$ be the trees in~$F_i$ containing $u$ and~$v$ respectively.
 \:If $n(T_1) > n(T_2)$, swap $T_1$ with~$T_2$.

-\:Move all level~$i$ edges in~$T_1$ to level~$i+1$ and insert them to~${\cal E}_{i+1}$.
+\:Find all level~$i$ edges in~$T_1$ using ${\cal E}_i$ and move them to level~$i+1$.

 \:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
   For each edge~$xy$, $x\in T_1$, do:
 \:Enumerate non-tree edges incident with vertices of~$T_1$ and stored in ${\cal E}_i$.
   For each edge~$xy$, $x\in T_1$, do:

-\::If $y\in T_2$, add the edge $xy$ to~$F_i$ and return.
-\::Otherwise increase $\ell(xy)$ by one. This includes deleting~$xy$ from~${\cal E}_i$
-  and inserting it to~${\cal E}_{i+1}$.
+\::If $y\in T_2$, remove~$xy$ from~${\cal E}_i$ and return it to the caller.
+\::Otherwise increase $\ell(xy)$ by one.
+  \hfil\break
+  This includes deleting~$xy$ from~${\cal E}_i$ and inserting it to~${\cal E}_{i+1}$.

 \:If $i>0$, call $\<Replace>(xy,i-1)$.
 \:If $i>0$, call $\<Replace>(xy,i-1)$.

+\:Otherwise return \<null>.
+\algout The replacement edge.

 \endalgo
 
 \endalgo
 

-\>Analysis of the time complexity is straightforward:
+\>As promised, time complexity will be analysed by amortization on the levels.

 
 \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%
 
 \thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}}\id{dyncon}%

-Dynamic connectivity can be maintained in time $\O(\log^2 n)$ amortized for both
+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
 \<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 have it pre-pay all level increases of the new
+(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.
 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.


@@ -488,19 +498,31 @@ ET-trees. Additionally, we call \<Replace> up to $L$ times. The initialization o
 \<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
 increases.
 
 \<Replace> costs $\O(\log n)$ per call, the rest is paid for by the edge level
 increases.
 

-To bring the complexity of \<Connected> from $\O(\log n)$ down to $\O(\log n/\log\log n)$,
+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
 
 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 MSF}
+\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
 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
+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 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


@@ -508,12 +530,12 @@ the same path. They have modified their dynamic connectivity algorithm to solve
 in $\O(\log^2 n)$ and obtained the fully dynamic MSF working in $\O(\log^4 n)$ per operation.
 
 \paran{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 decremental MSF requires only two
+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})
 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 try the lightest non-tree edge incident with the examined tree first. We must ensure
+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:
 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:


@@ -526,73 +548,79 @@ the following invariant:
 \endlist
 }
 
 \endlist
 }
 

-\>This easily implies that we select the right replacement edge:
+\>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
 
 \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 on the maximum level.
+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
 
 \proof
 Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle

-rule (\ref{cyclerule}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
+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.
 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 by I3 $f_1$~is the heaviest edge on~$C$, so
-$\ell(f_1) \le \ell(f_2)$. Therefore the lightest of all replacement edges must have
+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
 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$ between $F^a$ and~$F^b$ let $g^a$ and~$g^b$ be its respective endpoints.
+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 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 observed:
+We now have to make sure that the additional invariant is indeed observed:

 
 \lemma\id{ithree}%
 
 \lemma\id{ithree}%

-After every operation, I3 is satisfied.
+After every operation, the invariant I3 is satisfied.

 
 \proof
 
 \proof

-When the structure is freshly initialized, I3 is obviously satisfied, because all edges
+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
 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 when an~edge~$e$ either gets its level increased
-or becomes a~tree edge.
-
-For the violation to happen, $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 happen 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$.
-
-Let us first show that for edges of~$C$ incident with~$T_1$. All edges of~$T_1$ itself
-already are on the higher levels as they were moved there at the very beginning of the
-search for the replacement edge. As the algorithm always tries the lightest candidate
-for the replacement edge first, all non-tree edges incident with~$T_1$ which are lighter
-than~$e$ were already considered and thus also moved one level up. This includes all
-other edges of~$C$ that are incident with~$T_1$.
-
-The case of edges that do not touch~$T_1$ is easy to handle: Such edges do not exist.
-If they did, at least two edges of~$C$ would have to be non-tree edges connecting~$T_1$
-with the other trees at level~$\ell$, so one of them that is lighter than~$e$ would be selected as the
-replacement edge before~$e$ could be considered.
+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}}
 \qed
 
 We can conclude:
 
 \thmn{Decremental MSF, Holm et al.~\cite{holm:polylog}}

-When we start with a~graph with $n$~vertices and~$m\ge n$ edges and we perform
-$d$~edge deletions, the MSF can be maintained in time $\O((m+d)\cdot\log^2 n)$.
+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
 
 \paran{Fully dynamic MSF}%
 The decremental MSF algorithm can be turned to a~fully dynamic one by a~blackbox

-reduction whose properties are summarized by the following theorem:
+reduction whose properties are summarized in the following theorem:

 
 

-\thmn{MSF dynamization, Henzinger et al.~\cite{henzinger:twoec}, Holm et al.~\cite{holm:polylog}}
-Suppose that we have a~decremental MSF algorithm that for any $a$,~$b$ can be initialized
-on a~graph with~$a$ vertices and~$b$ edges and then it executes an~arbitrary sequence
-of deletions in time $\O(b\cdot t(a,b))$, where~$t$ is a~non-decreasing function.
-Then there exists a~fully dynamic MSF algorithm for a~graph on $n$~vertices, starting
+\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.}
 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.}


@@ -600,7 +628,7 @@ $$
 
 \proofsketch
 The reduction is very technical, but its essence is the following: We maintain a~logarithmic number
 
 \proofsketch
 The reduction is very technical, but its essence is the following: We maintain a~logarithmic number

-of decremental structures $A_0,\ldots,A_{\log n}$ of exponentially increasing sizes. Every non-tree
+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
 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


@@ -609,20 +637,20 @@ Delete of a~non-tree edge is performed on all $A_i$'s containing it and the repl
 sought among the replacement edges found in these structures. The unused replacement edges then have
 to be reinserted back to the structure.
 
 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.~handles the reinserts by a~mechanism of batch insertions
+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}
 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 amortized time $\O(\log^4 n)$
+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
 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 m)$ where~$m$
-is the number of operations performed. This could be more than $\O(\log^4 n)$ if
+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.
 $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.


@@ -630,33 +658,31 @@ rebuild then incurs only $\O(\log^4 n)$ additional cost on each operation.
 
 \rem
 The limitation of MSF structures based on the Holm's algorithm for connectivity
 
 \rem
 The limitation of MSF structures based on the Holm's algorithm for connectivity

-to edge deletions only seems to be unavoidable. The invariant I3 could be easily
+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
 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

-possibly hit I1 before we skipped the levels of all the heavies edges on the
+likely hit I1 before we managed to skip the levels of all the heaviest edges on the

 particular cycles.
 
 particular cycles.
 

-On the other hand, if we decided to drop I3, we would encounter different problems.
-We have enough time to scan all non-tree edges incident to the current tree~$T_1$
---- we can charge it on the level increases of its tree edges and if we use the
-degree reduction from Lemma \ref{degred}, there are at most two non-tree edges
-per vertex. (The reduction can be used dynamically as it always translates a~single
-change of the original graph to $\O(1)$ changes of the reduced graph.) The lightest
-replacement edge however could also be located in the super-trees of~$T_1$ on the
-lower levels, which are too large to scan and both I1 and I2 prevent us from
-charging the time on increasing levels there.
+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
 
 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.
+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
 
 \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 drop our rule that all edge weights are distinct for a~moment and we recall that
-the basic structural properties of the MST's from Section \ref{mstbasics} still hold.
+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
 
 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 to maintain
+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
 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


@@ -687,7 +713,7 @@ 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
 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$ and the MSF edges from~$\C_{i-1}$. Bounding the time complexity is then easy:
+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
 
 \thmn{MSF with limited edge weights}
 There is a~fully dynamic MSF algorithm that works in time $\O(k\cdot\log^2 n)$ amortized


@@ -697,7 +723,8 @@ per operation for graphs on $n$~vertices with only $k$~distinct edge weights all
 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
 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}.
+Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan trees
+by Theorem \ref{sletar}.

 \qed
 
 
 \qed