From ab8bd43d85295f57fa87bc0c3f86674b11303452 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 13:18:44 +0200 Subject: [PATCH] Fixes to dynamic MSF. --- dyn.tex | 57 +++++++++++++++++++++++++++++++-------------------------- 1 file changed, 31 insertions(+), 26 deletions(-) diff --git a/dyn.tex b/dyn.tex index 5aaee2a..7797c0b 100644 --- a/dyn.tex +++ b/dyn.tex @@ -561,28 +561,27 @@ the edges $f_1$ and~$f_2$, which together form a~simple cycle. We now have to make sure that the additional invariant is indeed observed: \lemma\id{ithree}% -After every operation, I3 is satisfied. +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 when an~edge~$e$ either gets its level increased -or it becomes a~tree edge. +to check only the replaces, in particular the place when an~edge~$e$ gets its level increased. 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 +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$. Let us first show that 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. As the algorithm always tries the lightest candidate -for the replacement edge first, all non-tree edges incident with~$T_1$ which are lighter +search for the replacement edge. As the algorithm always picks the lightest candidate +for the replacement edge available, all non-tree edges incident with~$T_1$ that 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. +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 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. @@ -591,18 +590,21 @@ replacement edge before~$e$ could be considered. 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 -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 +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.} @@ -610,7 +612,7 @@ $$ \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 @@ -619,20 +621,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. -The original reduction of Henzinger et al.~handles the reinserts by a~mechanism of batch insertions +The original reduction of Henzinger et al.~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 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 -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. @@ -640,10 +642,10 @@ 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 -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 -possibly hit I1 before we skipped the levels of all the heavies edges on the +possibly hit I1 before we skipped 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. @@ -658,15 +660,17 @@ 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. +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 drop our rule that all edge weights are distinct for a~moment and we recall that +1~and~2). We will forget 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. 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 @@ -697,7 +701,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 -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 @@ -707,7 +711,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 -Theorem \ref{dyncon}. +Theorem \ref{dyncon} and $\O(\log n)$ on operations with the Sleator-Tarjan trees +by Theorem \ref{sletar}. \qed -- 2.39.2