slides/slides.tex

   1 \documentclass{beamer}
   2 \usepackage[latin2]{inputenc}
   3 \usepackage{palatino}
   4 \usetheme{Warsaw}
   5 \title[Graph Algorithms]{Graph Algorithms\\Spanning Trees and Ranking}
   6 \author[Martin Mare¹]{Martin Mare¹\\\texttt{mares@kam.mff.cuni.cz}}
   7 \institute{Department of Applied Mathematics\\MFF UK Praha}
   8 \date{2008}
   9 \begin{document}
  10 \setbeamertemplate{navigation symbols}{}
  11 \setbeamerfont{title page}{family=\rmfamily}
  12
  13 \def\[#1]{\hskip0.3em{\color{violet} [#1]}}
  14 \def\O{{\cal O}}
  15
  16 \begin{frame}
  17 \titlepage
  18 \end{frame}
  19
  20 \begin{frame}{The Minimum Spanning Tree Problem}
  21
  22 {\bf 1. Minimum Spanning Tree Problem:}
  23
  24 \begin{itemize}
  25 \item Given a~weighted undirected graph,\\
  26   what is its lightest spanning tree?
  27 \item In fact, a~linear order on edges is sufficient.
  28 \item Efficient solutions are very old \[Borùvka 1926]
  29 \item A~long progression of faster and faster algorithms.
  30 \item Currently very close to linear time, but still not there.
  31 \end{itemize}
  32
  33 \end{frame}
  34
  35 \begin{frame}{The Ranking Problems}
  36
  37 {\bf 2. Ranking of Combinatorial Structures:}
  38
  39 \begin{itemize}
  40 \item We are given a~set~$C$ of objects with a~linear order $\prec$.
  41 \item {\bf Ranking function $R_\prec(x)$:} how many objects precede~$x$?
  42 \item {\bf Unranking function $R^{-1}_\prec(i)$:} what is the $i$-th object?
  43 \end{itemize}
  44
  45 \pause
  46
  47 \begin{example}[toy]
  48 $C=\{0,1\}^n$ with lexicographic order
  49
  50 \pause
  51 $R$ = conversion from binary\\
  52 $R^{-1}$ = conversion to binary
  53 \end{example}
  54
  55 \pause
  56 \begin{example}[a~real one]
  57 $C=$ set of all permutations on $\{1,\ldots,n\}$
  58 \end{example}
  59
  60 \pause
  61 How to compute the (un)ranking function efficiently?
  62
  63 For permutations, an $\O(n\log n)$ algorithm was known \[folklore].
  64
  65 We will show how to do that in $\O(n)$.
  66
  67 \end{frame}
  68
  69 \begin{frame}{Models of computation: RAM}
  70
  71 As we approach linear time, we must specify the model.
  72
  73 ~
  74
  75 {\bf 1. The Random Access Machine (RAM):}
  76
  77 \begin{itemize}
  78 \item Works with integers
  79 \item Memory: an array of integers indexed by integers
  80 \end{itemize}
  81
  82 ~
  83 \pause
  84
  85 Many variants exist, we will use the {\bf Word-RAM:}
  86
  87 \begin{itemize}
  88 \item Machine words of $W$ bits
  89 \item The ``C operations'': arithmetics, bitwise logical op's
  90 \item Unit cost
  91 \item We know that $W\ge\log_2 \vert \hbox{input} \vert$
  92 \end{itemize}
  93
  94 \end{frame}
  95
  96 \begin{frame}{Models of computation: PM}
  97
  98 {\bf 2. The Pointer Machine (PM):}
  99
 100 \begin{itemize}
 101 \item Memory cells accessed via pointers
 102 \item Each cell contains $\O(1)$ pointers and $\O(1)$ symbols
 103 \item Operates only on pointers and symbols
 104 \end{itemize}
 105
 106 ~
 107 \pause
 108
 109 \begin{beamerboxesrounded}[upper=block title example,shadow=true]{Key differences}
 110 \begin{itemize}
 111 \item PM has no arrays, we can emulate them in $\O(\log n)$ time.
 112 \item PM has no arithmetics.
 113 \end{itemize}
 114 \end{beamerboxesrounded}
 115
 116 ~
 117
 118 We can emulate PM on RAM with constant slowdown.
 119
 120 Emulation of RAM on PM is more expensive.
 121
 122 \end{frame}
 123
 124 \begin{frame}{PM Techniques}
 125
 126 {\bf Bucket Sorting} does not need arrays.
 127
 128 ~
 129
 130 Interesting consequences:
 131
 132 \begin{itemize}
 133 \item Flattening of multigraphs in $\O(m+n)$
 134 \item Unification of sequences in $\O(n+\sum_i\ell_i+\vert\Sigma\vert)$
 135 \item (Sub)tree isomorphism in $\O(n)$ simplified \[M. 2008]
 136 \item Batched graph computations \[Buchsbaum et al.~1998]
 137 \end{itemize}
 138
 139 \end{frame}
 140
 141 \begin{frame}{RAM Techniques}
 142
 143 We can use RAM as a vector machine:
 144
 145 ~
 146
 147 \begin{example}[parallel search]
 148 \def\sep{\;{\color{brown}0}}
 149 \def\seq{\;{\color{brown}1}}
 150 \def\sez{\;{\color{red}0}}
 151 We can encode the vector $(1,5,3,0)$ with 3-bit fields as:
 152 \begin{center}
 153 \sep001\sep101\sep011\sep000
 154 \end{center}
 155 And then search for 3 by:
 156
 157 \begin{center}
 158 \begin{tabular}{rcl}
 159           &\seq001\seq101\seq011\seq000 & $(1,5,3,0)$ \\
 160 {\sc xor} &\sep011\sep011\sep011\sep011 & $(3,3,3,3)$ \\
 161 \hline
 162           &\seq010\seq110\seq000\seq011 \\
 163 $-$       &\sep001\sep001\sep001\sep001 & $(1,1,1,1)$ \\
 164 \hline
 165           &\seq001\seq101\sez111\seq010 \\
 166 {\sc and} &\seq000\seq000\seq000\seq000 \\
 167 \hline
 168           &\seq000\seq000\sez000\seq000 \\
 169 \end{tabular}
 170 \end{center}
 171 \end{example}
 172
 173 \end{frame}
 174
 175 \begin{frame}{RAM Data Structures}
 176
 177 We can translate vector operations to $\O(1)$ RAM instructions
 178
 179 \smallskip
 180
 181 \dots\ as long as the vector fits in $\O(1)$ words.
 182
 183 ~
 184
 185 We can build ``small'' data structures operating in $\O(1)$ time:
 186
 187 \begin{itemize}
 188 \item Sets
 189 \item Ordered sets with ranking
 190 \item ``Small'' heaps of ``large'' integers \[Fredman \& Willard 1990]
 191 \end{itemize}
 192
 193 \end{frame}
 194
 195 \begin{frame}{Minimum Spanning Trees}
 196 Algorithms for Minimum Spanning Trees:
 197
 198 \begin{itemize}
 199 \item Classical algorithms \[Borùvka, Jarník-Prim, Kruskal]
 200 \item Contractive: $\O(m\log n)$ using flattening on the PM \\
 201       (lower bound \[M.])
 202 \item Iterated: $\O(m\,\beta(m,n))$ \[Fredman \& Tarjan~1987] \\
 203       where $\beta(m,n) = \min\{ k: \log_2^{(k)} n \le m/n \}$
 204 \item Even better: $\O(m\,\alpha(m,n))$ using {\it soft heaps}\hfil\break\[Chazelle 1998, Pettie 1999]
 205 \item MST verification: $\O(m)$ on RAM \[King 1997, M. 2008]
 206 \item Randomized: $\O(m)$ expected on RAM \[Karger et al.~1995]
 207 \end{itemize}
 208 \end{frame}
 209
 210 \begin{frame}{MST -- Special cases}
 211
 212 Cases for which we have an $\O(m)$ algorithm:
 213
 214 ~
 215
 216 Special graph structure:
 217
 218 \begin{itemize}
 219 \item Planar graphs \[Tarjan 1976, Matsui 1995, M. 2004] (PM)
 220 \item Minor-closed classes \[Tarjan 1983, M. 2004] (PM)
 221 \item Dense graphs (by many of the general PM algorithms)
 222 \end{itemize}
 223
 224 ~
 225 \pause
 226
 227 Or we can assume more about weights:
 228
 229 \begin{itemize}
 230 \item $\O(1)$ different weights \[folklore] (PM)
 231 \item Integer weights \[Fredman \& Willard 1990] (RAM)
 232 \item Sorted weights (RAM)
 233 \end{itemize}
 234
 235 \end{frame}
 236
 237 \begin{frame}{MST -- Optimality}
 238
 239 There is a~provably optimal comparison-based algorithm \\\[Pettie \& Ramachandran 2002]
 240
 241 ~
 242
 243 However, there is a catch\alt<2->{:}{ \dots} \pause Nobody knows its complexity.
 244
 245 ~
 246
 247 We know that it is $\O({\cal T}(m,n))$ where ${\cal T}(m,n)$ is the depth
 248 of the optimum MST decision tree. Any other algorithm provides an upper bound.
 249
 250 \pause
 251 ~
 252
 253 \begin{corollary}
 254 It runs on the PM, so we know that if there is a~linear-time algorithm,
 255 it does not need any special RAM data structures. (They can however
 256 help us to find it.)
 257 \end{corollary}
 258
 259 \end{frame}
 260
 261 \begin{frame}{MST -- Dynamic algorithms}
 262
 263 Sometimes, we need to find the MST of a~changing graph. \\
 264 We insert/delete edges, the structure responds with $\O(1)$
 265 modifications of the MST.
 266
 267 \begin{itemize}
 268 \item Unweighted cases, similar to dynamic connectivity:
 269   \begin{itemize}
 270   \item Incremental: $\O(\alpha(n))$ \[Tarjan 1975]
 271   \item Fully dynamic: $\O(\log^2 n)$ \[Holm et al.~2001]
 272   \end{itemize}
 273 \pause
 274 \item Weighted cases are harder:
 275   \begin{itemize}
 276   \item Decremental: $\O(\log^2 n)$ \[Holm et al.~2001]
 277   \item Fully dynamic: $\O(\log^4 n)$ \[Holm et al.~2001]
 278   \item Only~$C$ weights: $\O(C\log^2 n)$ \[M. 2008]
 279   \end{itemize}
 280 \pause
 281 \item $K$ smallest spanning trees:
 282   \begin{itemize}
 283   \item Simple: $\O(T_{MST} + Km)$ \[Katoh et al.~1981, M.~2008]
 284   \item Small~$K$: $\O(T_{MST} + \min(K^2, Km + K\log K))$ \[Eppst.~1992]
 285   \item Faster: $\O(T_{MST} + \min(K^{3/2}, Km^{1/2}))$ \[Frederickson 1997]
 286   \end{itemize}
 287 \end{itemize}
 288
 289 \end{frame}
 290
 291 \begin{frame}{Back to Ranking}
 292
 293 Ranking of permutations on the RAM: \[M. \& Straka 2007]
 294
 295 \begin{itemize}
 296 \item We need a DS for the subsets of $\{1,\ldots,n\}$ with ranking
 297 \item The result can be $n!$ $\Rightarrow$ word size is $\Omega(n\log n)$ bits
 298 \item We can represent the subsets as RAM vectors
 299 \item This gives us an~$\O(n)$ time algorithm for (un)ranking
 300 \end{itemize}
 301
 302 ~
 303
 304 Easily extendable to $k$-permutations, also in $\O(n)$
 305
 306 \end{frame}
 307
 308 \begin{frame}{Restricted permutations}
 309
 310 For restricted permutations (e.g., derangements): \[M. 2008]
 311
 312 \begin{itemize}
 313 \item Describe restrictions by a~bipartite graph
 314 \item Existence of permutation reduces to network flows
 315 \item The ranking function can be used to calculate permanents,\\
 316       so it is $\#\rm P$-complete
 317 \item However, this is the only obstacle. Calculating $\O(n)$
 318       sub-permanents is sufficient.
 319 \item For derangements, we have achieved $\O(n)$ time after $\O(n^2)$ time
 320       preprocessing.
 321 \end{itemize}
 322
 323 \end{frame}
 324
 325 \begin{frame}{Summary}
 326
 327 Summary:\\
 328
 329 \begin{itemize}
 330 \item Low-level algorithmic techniques on RAM and PM
 331 \item Generalized pointer-based sorting and RAM vectors
 332 \item Applied to a~variety of problems:
 333   \begin{itemize}
 334   \item A~short linear-time tree isomorphism algorithm
 335   \item A~linear-time algorithm for MST on minor-closed classes
 336   \item Corrected and simplified MST verification
 337   \item Dynamic MST with small weights
 338   \item {\it Ranking and unranking of permutations}
 339   \end{itemize}
 340 \item Also:
 341   \begin{itemize}
 342   \item A~lower bound for the Contractive Borùvka's algorithm
 343   \item Simplified soft-heaps
 344   \end{itemize}
 345 \end{itemize}
 346
 347 \end{frame}
 348
 349 \begin{frame}{Good Bye}
 350
 351 \bigskip
 352
 353 \centerline{\sc\huge The End}
 354
 355 \bigskip
 356
 357 \begin{figure}
 358 \pgfdeclareimage[width=0.3\hsize]{brum}{brum2.png}
 359 \pgfuseimage{brum}
 360 \end{figure}
 361
 362 \end{frame}
 363
 364 \end{document}