dyn.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Dynamic Spanning Trees}\id{dynchap}%
   6
   7 \section{Dynamic graph algorithms}
   8
   9 In many applications, we often need to solve a~certain graph problem for a~sequence
  10 of graphs that differ only a~little, so recomputing the solution from scratch for
  11 every graph would be a~waste of time. In such cases, we usually turn our attention
  12 to \df{dynamic graph algorithms.} A~dynamic algorithm is in fact a~data structure
  13 that remembers a~graph and offers operations that modify the structure of the graph
  14 (let's say by insertion and deletion of edges) and also operations that query the
  15 result of the problem for the current state of the graph.
  16 A~typical example of a~problem solved by such algorithms is dynamic maintenance of
  17 connected components:
  18
  19 \problemn{Dynamic connectivity}
  20 Maintain an~undirected graph under a~sequence of the following operations:
  21 \itemize\ibull
  22 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.\foot{%
  23 The structure could support dynamic addition and removal of vertices, too,
  24 but this is easy to add and infrequently used, so we will rather define
  25 the structure with a~fixed set of vertices for clarity.}
  26 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$ and return its unique
  27 identifier (assuming that the edge did not exist yet).
  28 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
  29 \:$\<Connected>(G,u,v)$ --- Test if $u$ and~$v$ are in the same connected component of~$G$.
  30 \endlist
  31
  32 \para
  33 We have already encountered a~special case of dynamic connectivity when implementing the
  34 Kruskal's algorithm in Section \ref{classalg}. At that time, we did not need to delete
  35 any edges from the graph, which makes the problem substantially easier. This special
  36 case is sometimes called an~\df{incremental} or \df{semidynamic} graph algorithm.
  37 We mentioned the Union-Find data structure of Tarjan and van Leeuwen \cite{tarjan:setunion}
  38 which can be used for that: queries on connectedness translate to \<Find>, edge
  39 insertions to \<Find> followed by \<Union> if the edge connects two different
  40 components. This way, a~sequence of $m$~operations starting with an~empty graph
  41 on $n$~vertices is processed in time $\O(m\timesalpha(m,n))$ and this works even
  42 on the Pointer Machine. Fredman and Saks \cite{fredman:cellprobe} have proven
  43 a~matching lower bound in the cell-probe model which is stronger than RAM with
  44 $\O(\log n)$-bit words.
  45
  46 The edges that have triggered the \<Union>s form a~spanning forest of the current graph.
  47 So far, all known algorithms for dynamic connectivity maintain some sort of a~spanning
  48 tree. This suggests that a~dynamic MST algorithm could be obtained by modifying the
  49 dynamic connectivity algorithms. This will indeed turn out to be true. Semidynamic MST
  50 is easy to achieve even in the few pages of this section, but making it fully dynamic will require
  51 more effort, so we will review some of the required building blocks before going into that.
  52
  53 We however have to answer one important question first: What should be the output of
  54 our MSF data structure? Adding an~operation that would return the MSF of the current
  55 graph is of course possible, but somewhat impractical as this operation has to
  56 spend $\Omega(n)$ time on the mere writing of its output. A~better way seems to
  57 be to make the \<Insert> and \<Delete> operations report the list of modifications
  58 of the MSF caused by the change in the graph.
  59
  60 Let us see what happens when we \<Insert> an~edge~$e$ to a~graph~$G$ with a~minimum spanning
  61 forest~$F$, obtaining a~new graph~$G'$ with its MSF~$F'$. If $e$~connects two components of~$G$ (and
  62 therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the following cases happens:
  63 Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light
  64 and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$.
  65
  66 Correctness of the former case follows immediately from the Theorem on Minimality by order
  67 (\ref{mstthm}), because all $F'$-light would be also $F$-light, which is impossible as $F$~was
  68 minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest
  69 on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma
  70 (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$
  71 of~$F$ containing both endpoints of the edge~$e$. When we remove~$f$ from~$F$, this tree falls
  72 apart to two components $T_1$ and~$T_2$. The edge~$f$ was the lightest edge of the cut~$\delta_G(T_1)$
  73 and $e$~is lighter than~$f$, so $e$~is the lightest in~$\delta_{G'}(T_1)$ and hence $e\in F'$.
  74
  75 A~\<Delete> of an~edge that is not contained in~$F$ does not change~$F$. When we delete
  76 an~MSF edge, we have to reconnect~$F$ by choosing the lightest edge of the cut separating
  77 the new components. If there is no such replacement edge, we have deleted a~bridge,
  78 so the MSF has to remain disconnected.
  79
  80 The idea of reporting differences in the MSF indeed works very well. We can summarize
  81 what we have shown by the following lemma and use it to define the dynamic MSF.
  82
  83 \lemma
  84 An~\<Insert> or \<Delete> of an~edge in~$G$ causes at most one edge addition, edge
  85 removal or edge exchange in $\msf(G)$.
  86
  87 \problemn{Dynamic minimum spanning forest}
  88 Maintain an~undirected graph with weights on edges (drawn from a~totally ordered set)
  89 and its minimum spanning forest under a~sequence of the following operations:
  90 \itemize\ibull
  91 \:$\<Init>(n)$ --- Create a~graph with $n$~isolated vertices $\{1,\ldots,n\}$.
  92 \:$\<Insert>(G,u,v)$ --- Insert an~edge $uv$ to~$G$. Return its unique
  93         identifier and the list of additions and deletions of edges in $\msf(G)$.
  94 \:$\<Delete>(G,e)$ --- Delete an~edge specified by its identifier from~$G$.
  95         Return the list of additions and deletions of edges in $\msf(G)$.
  96 \endlist
  97
  98 \paran{Semidynamic MSF}%
  99 To obtain a~semidynamic MSF algorithm, we need to keep the forest in a~data structure which
 100 supports search for the heaviest edge on the path connecting a~given pair
 101 of vertices. This can be handled efficiently by the Link-Cut trees of Sleator and Tarjan:
 102
 103 \thmn{Link-Cut Trees, Sleator and Tarjan \cite{sleator:trees}}\id{sletar}%
 104 There is a~data structure that represents a~forest of rooted trees on~$n$ vertices.
 105 Each edge of the forest has a~weight drawn from a~totally ordered set. The structure
 106 supports the following operations in time $\O(\log n)$ amortized:\foot{%
 107 The Link-Cut trees offer many other operations, but we do not mention them
 108 as they are not needed in our application.}
 109 \itemize\ibull
 110 \:$\<Parent>(v)$ --- Return the parent of~$v$ in its tree or \<null> if $v$~is a~root.
 111 \:$\<Root>(v)$ --- Return the root of the tree containing~$v$.
 112 \:$\<Weight>(v)$ --- Return the weight of the edge $(\<Parent(v)>,v)$.
 113 \:$\<PathMax>(v)$ --- Return the vertex~$w$ closest to $\<Root>(v)$ such that the edge
 114         $(\<Parent>(w),w)$ is the heaviest of those on the path from~$v$ to the root.
 115         If more edges have the maximum weight, break the tie arbitrarily.
 116         If there is no such edge ($v$~is the root itself), return \<null>.
 117 \:$\<Link>(u,v,x)$ --- Connect the trees containing $u$ and~$v$ by an~edge $(u,v)$ of
 118         weight~$x$. Assumes that $u~$is a tree root and $v$~lies in a~different tree.
 119 \:$\<Cut>(v)$ --- Split the tree containing the non-root vertex $v$ to two trees by
 120         removing the edge $(v,\<Parent>(v))$. Returns the weight of this edge.
 121 \:$\<Evert>(v)$ --- Modify the orientations of the edges in the tree containing~$v$
 122         to make~$v$ the tree's root.
 123 \endlist
 124
 125 %% \>Additionally, all edges on the path from~$v$ to $\<Root>(v)$ can be enumerated in
 126 %% time $\O(\ell + \log n)$, where $\ell$~is the length of that path. This operation
 127 %% (and also the path itself) is called $\<Path>(v)$.
 128 %%
 129 %% \>If the weights are real numbers (or in general an~arbitrary group), the $\O(\log n)$
 130 %% operations also include:
 131 %%
 132 %% \itemize\ibull
 133 %% \:$\<PathWeight>(v)$ --- Return the sum of the weights on $\<Path>(v)$.
 134 %% \:$\<PathUpdate>(v,x)$ --- Add~$x$ to the weights of all edges on $\<Path>(v)$.
 135 %% \endlist
 136
 137 \proof
 138 See \cite{sleator:trees}.
 139 \qed
 140
 141 Once we have this structure, we can turn our ideas on updating of the MSF to
 142 an~algorithm:
 143
 144 \algn{\<Insert> in a~semidynamic MSF}
 145 \algo
 146 \algin A~graph~$G$ with its MSF $F$ represented as a~Link-Cut forest, an~edge~$uv$
 147 with weight~$w$ to be inserted.
 148 \:$\<Evert>(u)$. \cmt{$u$~is now the root of its tree.}
 149 \:If $\<Root>(v) \ne u$: \cmt{$u$~and~$v$ lie in different trees.}
 150 \::$\<Link>(u,v,w)$. \cmt{Connect the trees.}
 151 \::Return ``$uv$ added''.
 152 \:Otherwise:
 153 \::$y\=\<PathMax>(v)$.
 154 \::$x\=\<Parent>(x)$.  \cmt{Edge~$xy$ is the heaviest on $F[uv]$.}
 155 \::If $\<Weight>(x) > w$: \cmt{We have to exchange~$xy$ with~$uv$.}
 156 \:::$\<Cut>(x)$, $\<Evert>(v)$, $\<Link>(v,y,w)$.
 157 \:::Return ``$uv$~added, $xy$~removed''.
 158 \::Otherwise return ``no changes''.
 159 \algout The list of changes in~$F$.
 160 \endalgo
 161
 162 \thmn{Semidynamic MSF}
 163 When only edge insertions are allowed, the MSF can be maintained in time $\O(\log n)$
 164 amortized per operation.
 165
 166 \proof
 167 Every \<Insert> performs $\O(1)$ operations on the Link-Cut forest, which take
 168 $\O(\log n)$ each by Theorem \ref{sletar}.
 169 \qed
 170
 171
 172 %--------------------------------------------------------------------------------
 173
 174 \section{ET trees}
 175
 176
 177 \endpart