From 13bbbd56bd577b4d5bb856da3ab6e1ae6392300d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 15 Apr 2008 22:18:56 +0200 Subject: [PATCH] Fully dynamic MSF. Unfortunately not my algorithm as it was found to be fatally broken. --- PLAN | 6 +- dyn.tex | 241 +++++++++++++++++++++++++++++++++++++++++++++++++++----- mst.tex | 2 +- 3 files changed, 226 insertions(+), 23 deletions(-) diff --git a/PLAN b/PLAN index 11f71ac..8290453 100644 --- a/PLAN +++ b/PLAN @@ -32,9 +32,9 @@ * Dynamic MST algorithms o (Semi-)dynamic algorithms - . ET-trees - . Fully dynamic connectivity - . Dynamic MST + o ET-trees + o Fully dynamic connectivity + o Dynamic MST * Ranking Combinatorial Objects diff --git a/dyn.tex b/dyn.tex index 4f4f7ae..5b11a08 100644 --- a/dyn.tex +++ b/dyn.tex @@ -46,7 +46,7 @@ words. The edges that have triggered the \s form a~spanning forest of the current graph. So far, all known algorithms for dynamic connectivity maintain some sort of a~spanning tree. This suggests that a~dynamic MST algorithm could be obtained by modifying the -dynamic connectivity algorithms. This will indeed turn out to be true. Semidynamic MST +dynamic connectivity algorithms. This will indeed turn out to be true. Incremental MST is easy to achieve even in the few pages of this section, but making it fully dynamic will require more effort, so we will review some of the required building blocks before going into that. @@ -96,8 +96,8 @@ and its minimum spanning forest under a~sequence of the following operations: Return the list of additions and deletions of edges in $\msf(G)$. \endlist -\paran{Semidynamic MSF}% -To obtain a~semidynamic MSF algorithm, we need to keep the forest in a~data structure that +\paran{Incremental MSF}% +To obtain an~incremental MSF algorithm, we need to keep the forest in a~data structure that supports search for the heaviest edge on the path connecting a~given pair of vertices. This can be handled efficiently by the Link-Cut trees of Sleator and Tarjan: @@ -142,7 +142,7 @@ See \cite{sleator:trees}. Once we have this structure, we can turn our ideas on updating of the MSF to an~incremental algorithm: -\algn{\ in a~semidynamic MSF} +\algn{\ in an~incremental MSF} \algo \algin A~graph~$G$ with its MSF $F$ represented as a~Link-Cut forest, an~edge~$uv$ with weight~$w$ to be inserted. @@ -286,6 +286,7 @@ data structure. The structure consists of: \:$\(e)$ --- Delete a~non-tree edge~$e$ given by its identifier. \:$\(v)$ --- Return non-tree edges stored in the same tree as~$v$. \endlist +\>If the non-tree edges have weights, \impl We will implement the operations on the ET-trees by translating the intended changes of the @@ -340,6 +341,29 @@ in the graph. If we keep the spanning forest in ET-trees with $a=\log n$, the up data structure cost an~extra $\O(\log^2 n / \log\log n)$, but queries accelerate to $\O(\log n/\log\log n)$. +\paran{ET-trees with weights} +In some cases, we will also need to represent weighted graphs and enumerate the non-tree +edges in order of their increasing weights (in fact, it will be sufficient to find the +lightest one, remove it and iterate). This can be handled by a~minute modification of the +ET-trees. + +The tree edges will remember their weight in the corresponding internal keys of the ET-tree. +We replace each list of non-tree edges by an~$(a,b)$-tree keeping the edges sorted by weight. +We also store the minimum element of the tree separately, so that it can be accessed in constant +time. The boolean \em{marker} will then become the minimum weight of a~non-tree edge attached to the +particular subtree, which can be recalculated as easy as the markers can. Searching for the +lightest non-tree edge then just follows the modified markers. + +The time complexities of all operations therefore remain the same, with a~possible +exception of the operations on non-tree edges, to which we have added the burden of +updating the new $(a,b)$-trees. This however consists of $\O(1)$ updates per a~single +call to \ or \, which takes $\O(a\log_a n)$ time only. +We can therefore conclude: + +\corn{Weighted ET-trees}\id{wtet}% +The time bounds in Theorem \ref{etthm} hold for the weighted ET-trees, too. + + %-------------------------------------------------------------------------------- \section{Dynamic connectivity} @@ -426,8 +450,7 @@ level~$i$ will be attached to its vertices. \algo \: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$. -\:Increase levels of all edges in~$T_1$ to~$i+1$ and insert them to~${\cal E}_{i+1}$ - where needed. +\:Move all level~$i$ edges in~$T_1$ to level~$i+1$ and insert them to~${\cal E}_{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: \::If $y\in T_2$, add the edge $xy$ to~$F_i$ and return. @@ -438,7 +461,7 @@ level~$i$ will be attached to its vertices. \>Analysis of the time complexity is straightforward: -\thmn{Fully dynamic connectivity, Holm et al.~\cite{holm:polylog}} +\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 \ and \ and in time $\O(\log n/\log\log n)$ per \ in the worst case. @@ -470,22 +493,202 @@ have generalized their randomized connectivity algorithm to maintain the MSF in 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. -Holm, de Lichtenberg and Thorup \cite{holm:polylog} 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. +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 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 try 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 easily implies that we 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 on 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 (\ref{cyclerule}), 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 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 +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. +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: + +\lemma\id{ithree}% +After every operation, I3 is satisfied. + +\proof +When the structure is freshly initialized, I3 is obviously satisfied, because 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 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. +\qed -We will present a~new algorithm which will reach the same time complexity in -a~much easier way, and which also behaves better when the set of possible -weights small (of size at most $\poly(n)$). The algorithm is based on -a~different idea: We will first observe that the dynamic connectivity algorithm -described in the previous section can be used for maintaining the MSF in time -$\O(\log^2 n)$ if only two values of edge weights are allowed. This will serve -as a~building block in an~$\O(\log k\cdot\log^2 n)$ time algorithm for -$k$~different edge weights. Finally, partial rebuilding of this structure -will bring the $\O(\log^4 n)$ bound for the MSF with unrestricted weights. +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)$. + +\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: + +\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 +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_{\log n}$ 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.~handles the 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)$ +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 +$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 edge deletions only 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 +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. + +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. + +\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. + +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 +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$ and 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}. +\qed \endpart diff --git a/mst.tex b/mst.tex index e931d1d..963e068 100644 --- a/mst.tex +++ b/mst.tex @@ -53,7 +53,7 @@ also presents several new ones. %-------------------------------------------------------------------------------- -\section{Basic properties} +\section{Basic properties}\id{mstbasics}% In this section, we will examine the basic properties of spanning trees and prove several important theorems to base the algorithms upon. We will follow the theory -- 2.39.5