From 5a80c7a83690193aadbb716b196231b97a5b09ca Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 12:19:16 +0200 Subject: [PATCH] Corrections to the intro to dynamic algorithms. --- PLAN | 3 +++ dyn.tex | 58 ++++++++++++++++++++++++++++++--------------------------- 2 files changed, 34 insertions(+), 27 deletions(-) diff --git a/PLAN b/PLAN index 3ef63c6..9357147 100644 --- a/PLAN +++ b/PLAN @@ -60,6 +60,8 @@ Spanning trees: - mention bugs in Valeria's verification paper - more references on decision trees - rename theorem on Minimality by order +- introduce Cut rule and Cycle rule earlier +- Lemma: deletion of a non-MST edge does not alter the MST Related: - practical considerations: katriel:cycle, moret:practice (mention pairing heaps) @@ -84,6 +86,7 @@ Models: Dynamic: - What is the origin of the semidynamic MSF? +- lower bounds Ranking: diff --git a/dyn.tex b/dyn.tex index 5b11a08..5a7a879 100644 --- a/dyn.tex +++ b/dyn.tex @@ -6,14 +6,13 @@ \section{Dynamic graph algorithms} -In many applications, we often need to solve a~certain graph problem for a~sequence -of graphs that differ only a~little, so recomputing the solution from scratch for -every graph would be a~waste of time. In such cases, we usually turn our attention -to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure -that remembers a~graph and offers operations that modify the structure of the graph -and also operations that query the result of the problem for the current state -of the graph. A~typical example of a~problem of this kind is dynamic -maintenance of connected components: +In many applications, we often need to solve a~certain graph problem for a~sequence of graphs that +differ only a~little, so recomputing the solution for every graph from scratch would be a~waste of +time. In such cases, we usually turn our attention to \df{dynamic graph algorithms.} A~dynamic +algorithm is in fact a~data structure that remembers a~graph. It offers operations that modify the +structure of the graph and also operations that query the result of the problem for the current +state of the graph. A~typical example of a~problem of this kind is dynamic maintenance of connected +components: \problemn{Dynamic connectivity} Maintain an~undirected graph under a~sequence of the following operations: @@ -25,7 +24,7 @@ of vertices fixed for clarity.} \:$\(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique identifier. This assumes that the edge did not exist yet. \:$\(G,e)$ --- Delete an~edge specified by its identifier from~$G$. -\:$\(G,u,v)$ --- Test if $u$ and~$v$ are in the same connected component of~$G$. +\:$\(G,u,v)$ --- Test if vertices $u$ and~$v$ are in the same connected component of~$G$. \endlist \para @@ -34,7 +33,7 @@ Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to any edges from the graph, which makes the problem substantially easier. This special case is customarily called an~\df{incremental} or \df{semidynamic} graph algorithm. We mentioned the Disjoint Set Union data structure of Tarjan and van Leeuwen (Theorem \ref{dfu}) -which can be used for that: Connected components are represented as an~equivalence classes. +which can be used for that: Connected components are represented by equivalence classes. Queries on connectedness translate to \, edge insertions to \ followed by \ if the new edge joins two different components. This way, a~sequence of $m$~operations starting with an~empty graph on $n$~vertices is @@ -43,12 +42,18 @@ Machine. Fredman and Saks \cite{fredman:cellprobe} have proven a~matching lower bound in the cell-probe model which is stronger than RAM with $\O(\log n)$-bit 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. 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. +In this chapter, we will focus on the dynamic version of the minimum spanning forest. +This problem seems to be intimately related to the dynamic connectivity. Indeed, all known +algorithms for dynamic connectivity maintain some sort of a~spanning forest. For example, in the +incremental algorithm we have just mentioned, this forest is formed by the edges that have +triggered the \s. This suggests that a~dynamic MSF algorithm could be obtained by modifying +the mechanism to keep the forest minimum. This will indeed turn out to be true, although we cannot +be sure that it will lead to the most efficient solution possible --- as of now, the known lower +bounds are very far. + +Incremental MST will be 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. We however have to answer one important question first: What should be the output of our MSF data structure? Adding an~operation that would return the MSF of the current @@ -64,12 +69,12 @@ Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. 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 all $F'$-light would be also $F$-light, which is impossible as $F$~was +(\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$ of~$F$ that contains both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls -apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest edge of the cut~$\delta_G(T_1)$ +apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest in the cut~$\delta_G(T_1)$ and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$. A~\ of an~edge that is not contained in~$F$ does not change~$F$. When we delete @@ -105,7 +110,7 @@ of vertices. This can be handled efficiently by the Link-Cut trees of Sleator an There is a~data structure that represents a~forest of rooted trees on~$n$ vertices. Each edge of the forest has a~weight drawn from a~totally ordered set. The structure supports the following operations in time $\O(\log n)$ amortized:\foot{% -The Link-Cut trees offer many other operations, but we do not mention them +The Link-Cut trees can offer a~plethora of other operations, but we do not mention them as they are not needed in our application.} \itemize\ibull \:$\(v)$ --- Return the parent of~$v$ in its tree or \ if $v$~is a~root. @@ -116,11 +121,10 @@ as they are not needed in our application.} If more edges have the maximum weight, break the tie arbitrarily. If there is no such edge ($v$~is the root itself), return \. \:$\(u,v,x)$ --- Connect the trees containing $u$ and~$v$ by an~edge $(u,v)$ of - weight~$x$. Assumes that $u~$is a tree root and $v$~lies in a~different tree. + weight~$x$. Assumes that $v~$is a tree root and $u$~lies in a~different tree. \:$\(v)$ --- Split the tree containing the non-root vertex $v$ to two trees by removing the edge $(\(v),v)$. Returns the weight of this edge. -\:$\(v)$ --- Modify the orientations of the edges in the tree containing~$v$ - to make~$v$ the tree's root. +\:$\(v)$ --- Modify the orientations of edges to make~$v$ the root of its tree. \endlist %% \>Additionally, all edges on the path from~$v$ to $\(v)$ can be enumerated in @@ -148,13 +152,13 @@ an~incremental algorithm: with weight~$w$ to be inserted. \:$\(u)$. \cmt{$u$~is now the root of its tree.} \:If $\(v) \ne u$: \cmt{$u$~and~$v$ lie in different trees.} -\::$\(u,v,w)$. \cmt{Connect the trees.} +\::$\(v,u,w)$. \cmt{Connect the trees.} \::Return ``$uv$ added''. \:Otherwise: \cmt{both are in the same tree} \::$y\=\(v)$. \::$x\=\(y)$. \cmt{Edge~$xy$ is the heaviest on $F[uv]$.} \::If $\(y) > w$: \cmt{We have to exchange~$xy$ with~$uv$.} -\:::$\(y)$, $\(v)$, $\(v,y,w)$. +\:::$\(y)$, $\(v)$, $\(u,v,w)$. \:::Return ``$uv$~added, $xy$~removed''. \::Otherwise return ``no changes''. \algout The list of changes in~$F$. @@ -178,7 +182,7 @@ What are the obstacles to making the structure fully dynamic? Deletion of edges that do not belong to the MSF is trivial (we do not need to change anything) and so is deletion of bridges (we just remove the bridge from the Link-Cut tree, knowing that there is no edge to replace it). The hard part -is the search for replacement edges after an~edge of the MSF is deleted. +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. @@ -189,8 +193,8 @@ we will take a~look on them first. An~important stop on the road to fully dynamic algorithms has the name \df{Eulerian Tour trees} or simply \df{ET-trees}. It is a~representation of forests introduced by Henzinger and King -\cite{henzinger:randdyn} in their randomized dynamic algorithms. It is similar to the one by Sleator -and Tarjan, but it is much simpler and instead of path operations it offers efficient operations on +\cite{henzinger:randdyn} in their randomized dynamic algorithms. It is similar to the Link-Cut +trees, but it is much simpler and instead of path operations it offers efficient operations on subtrees. It is also possible to attach auxiliary data to vertices and edges of the original tree. \defn\id{eulseq}% -- 2.39.2