\documentclass{beamer}
\usepackage[latin2]{inputenc}
\usepackage{palatino}
\usetheme{Warsaw}
\title[Graph Algorithms]{Graph Algorithms\\Spanning Trees and Ranking}
\author[Martin Mareš]{Martin Mareš\\\texttt{mares@kam.mff.cuni.cz}}
\institute{Department of Applied Mathematics\\MFF UK Praha}
\date{2008}
\begin{document}
\setbeamertemplate{navigation symbols}{}
\setbeamerfont{title page}{family=\rmfamily}

\def\[#1]{\hskip0.3em{\color{violet} [#1]}}
\def\O{{\cal O}}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}{The Minimum Spanning Tree Problem}

{\bf 1. Minimum Spanning Tree Problem:}

\begin{itemize}
\item Given a~weighted undirected graph,\\
  what is its lightest spanning tree?
\item In fact, a~linear order on edges is sufficient.
\item Efficient solutions are very old \[Borůvka 1926]
\item A~long progression of faster and faster algorithms.
\item Currently very close to linear time, but still not there.
\end{itemize}

\end{frame}

\begin{frame}{The Ranking Problems}

{\bf 2. Ranking of Combinatorial Structures:}

\begin{itemize}
\item We are given a~set~$C$ of objects with a~linear order $\prec$.
\item {\bf Ranking function $R_\prec(x)$:} how many objects precede~$x$?
\item {\bf Unranking function $R^{-1}_\prec(i)$:} what is the $i$-th object?
\end{itemize}

\pause

\begin{example}[toy]
$C=\{0,1\}^n$ with lexicographic order

\pause
$R$ = conversion from binary\\
$R^{-1}$ = conversion to binary
\end{example}

\pause
\begin{example}[a~real one]
$C=$ set of all permutations on $\{1,\ldots,n\}$
\end{example}

\pause
How to compute the (un)ranking function efficiently?

For permutations, an $\O(n\log n)$ algorithm was known \[folklore].

We will show how to do that in $\O(n)$.

\end{frame}

\begin{frame}{Models of computation: RAM}

As we approach linear time, we must specify the model.

~

{\bf 1. The Random Access Machine (RAM):}

\begin{itemize}
\item Works with integers
\item Memory: an array of integers indexed by integers
\end{itemize}

~
\pause

Many variants exist, we will use the {\bf Word-RAM:}

\begin{itemize}
\item Machine words of $W$ bits
\item The ``C operations'': arithmetics, bitwise logical op's
\item Unit cost
\item We know that $W\ge\log_2 \vert \hbox{input} \vert$
\end{itemize}

\end{frame}

\begin{frame}{Models of computation: PM}

{\bf 2. The Pointer Machine (PM):}

\begin{itemize}
\item Memory cells accessed via pointers
\item Each cell contains $\O(1)$ pointers and $\O(1)$ symbols
\item Operates only on pointers and symbols
\end{itemize}

~
\pause

\begin{beamerboxesrounded}[upper=block title example,shadow=true]{Key differences}
\begin{itemize}
\item PM has no arrays, we can emulate them in $\O(\log n)$ time.
\item PM has no arithmetics.
\end{itemize}
\end{beamerboxesrounded}

~

We can emulate PM on RAM with constant slowdown.

Emulation of RAM on PM is more expensive.

\end{frame}

\begin{frame}{PM Techniques}

{\bf Bucket Sorting} does not need arrays.

~

Interesting consequences:

\begin{itemize}
\item Flattening of multigraphs in $\O(m+n)$
\item Unification of sequences in $\O(n+\sum_i\ell_i+\vert\Sigma\vert)$
\item (Sub)tree isomorphism in $\O(n)$ simplified \[M. 2008]
\item Batched graph computations \[Buchsbaum et al.~1998]
\end{itemize}

\end{frame}

\begin{frame}{RAM Techniques}

We can use RAM as a vector machine:

~

\begin{example}[parallel search]
\def\sep{\;{\color{brown}0}}
\def\seq{\;{\color{brown}1}}
\def\sez{\;{\color{red}0}}
We can encode the vector $(1,5,3,0)$ with 3-bit fields as:
\begin{center}
\sep001\sep101\sep011\sep000
\end{center}
And then search for 3 by:

\begin{center}
\begin{tabular}{rcl}
          &\seq001\seq101\seq011\seq000 & $(1,5,3,0)$ \\
{\sc xor} &\sep011\sep011\sep011\sep011 & $(3,3,3,3)$ \\
\hline
          &\seq010\seq110\seq000\seq011 \\
$-$	  &\sep001\sep001\sep001\sep001 & $(1,1,1,1)$ \\
\hline
          &\seq001\seq101\sez111\seq010 \\
{\sc and} &\seq000\seq000\seq000\seq000 \\
\hline
          &\seq000\seq000\sez000\seq000 \\
\end{tabular}
\end{center}
\end{example}

\end{frame}

\begin{frame}{RAM Data Structures}

We can translate vector operations to $\O(1)$ RAM instructions

\smallskip

\dots\ as long as the vector fits in $\O(1)$ words.

~

We can build ``small'' data structures operating in $\O(1)$ time:

\begin{itemize}
\item Sets
\item Ordered sets with ranking
\item ``Small'' heaps of ``large'' integers \[Fredman \& Willard 1990]
\end{itemize}

\end{frame}

\begin{frame}{Minimum Spanning Trees}
Algorithms for Minimum Spanning Trees:

\begin{itemize}
\item Classical algorithms \[Borůvka, Jarník-Prim, Kruskal]
\item Contractive: $\O(m\log n)$ using flattening on the PM \\
      (lower bound \[M.])
\item Iterated: $\O(m\,\beta(m,n))$ \[Fredman \& Tarjan~1987] \\
      where $\beta(m,n) = \min\{ k: \log_2^{(k)} n \le m/n \}$
\item Even better: $\O(m\,\alpha(m,n))$ using {\it soft heaps}\hfil\break\[Chazelle 1998, Pettie 1999]
\item MST verification: $\O(m)$ on RAM \[King 1997, M. 2008]
\item Randomized: $\O(m)$ expected on RAM \[Karger et al.~1995]
\end{itemize}
\end{frame}

\begin{frame}{MST -- Special cases}

Cases for which we have an $\O(m)$ algorithm:

~

Special graph structure:

\begin{itemize}
\item Planar graphs \[Tarjan 1976, Matsui 1995, M. 2004] (PM)
\item Minor-closed classes \[Tarjan 1983, M. 2004] (PM)
\item Dense graphs (by many of the general PM algorithms)
\end{itemize}

~
\pause

Or we can assume more about weights:

\begin{itemize}
\item $\O(1)$ different weights \[folklore] (PM)
\item Integer weights \[Fredman \& Willard 1990] (RAM)
\item Sorted weights (RAM)
\end{itemize}

\end{frame}

\begin{frame}{MST -- Optimality}

There is a~provably optimal comparison-based algorithm \\\[Pettie \& Ramachandran 2002]

~

However, there is a catch\alt<2->{:}{ \dots} \pause Nobody knows its complexity.

~

We know that it is $\O({\cal T}(m,n))$ where ${\cal T}(m,n)$ is the depth
of the optimum MST decision tree. Any other algorithm provides an upper bound.

\pause
~

\begin{corollary}
It runs on the PM, so we know that if there is a~linear-time algorithm,
it does not need any special RAM data structures. (They can however
help us to find it.)
\end{corollary}

\end{frame}

\begin{frame}{MST -- Dynamic algorithms}

Sometimes, we need to find the MST of a~changing graph. \\
We insert/delete edges, the structure responds with $\O(1)$
modifications of the MST.

\begin{itemize}
\item Unweighted cases, similar to dynamic connectivity:
  \begin{itemize}
  \item Incremental: $\O(\alpha(n))$ \[Tarjan 1975]
  \item Fully dynamic: $\O(\log^2 n)$ \[Holm et al.~2001]
  \end{itemize}
\pause
\item Weighted cases are harder:
  \begin{itemize}
  \item Decremental: $\O(\log^2 n)$ \[Holm et al.~2001]
  \item Fully dynamic: $\O(\log^4 n)$ \[Holm et al.~2001]
  \item Only~$C$ weights: $\O(C\log^2 n)$ \[M. 2008]
  \end{itemize}
\pause
\item $K$ smallest spanning trees:
  \begin{itemize}
  \item Simple: $\O(T_{MST} + Km)$ \[Katoh et al.~1981, M.~2008]
  \item Small~$K$: $\O(T_{MST} + \min(K^2, Km + K\log K))$ \[Eppst.~1992]
  \item Faster: $\O(T_{MST} + \min(K^{3/2}, Km^{1/2}))$ \[Frederickson 1997]
  \end{itemize}
\end{itemize}

\end{frame}

\begin{frame}{Back to Ranking}

Ranking of permutations on the RAM: \[M. \& Straka 2007]

\begin{itemize}
\item We need a DS for the subsets of $\{1,\ldots,n\}$ with ranking
\item The result can be $n!$ $\Rightarrow$ word size is $\Omega(n\log n)$ bits
\item We can represent the subsets as RAM vectors
\item This gives us an~$\O(n)$ time algorithm for (un)ranking
\end{itemize}

~

Easily extendable to $k$-permutations, also in $\O(n)$

\end{frame}

\begin{frame}{Restricted permutations}

For restricted permutations (e.g., derangements): \[M. 2008]

\begin{itemize}
\item Describe restrictions by a~bipartite graph
\item Existence of permutation reduces to network flows
\item The ranking function can be used to calculate permanents,\\
      so it is $\#\rm P$-complete
\item However, this is the only obstacle. Calculating $\O(n)$
      sub-permanents is sufficient.
\item For derangements, we have achieved $\O(n)$ time after $\O(n^2)$ time
      preprocessing.
\end{itemize}

\end{frame}

\begin{frame}{Summary}

Summary:\\

\begin{itemize}
\item Low-level algorithmic techniques on RAM and PM
\item Generalized pointer-based sorting and RAM vectors
\item Applied to a~variety of problems:
  \begin{itemize}
  \item A~short linear-time tree isomorphism algorithm
  \item A~linear-time algorithm for MST on minor-closed classes
  \item Corrected and simplified MST verification
  \item Dynamic MST with small weights
  \item {\it Ranking and unranking of permutations}
  \end{itemize}
\item Also:
  \begin{itemize}
  \item A~lower bound for the Contractive Borůvka's algorithm
  \item Simplified soft-heaps
  \end{itemize}
\end{itemize}

\end{frame}

\begin{frame}{Good Bye}

\bigskip

\centerline{\sc\huge The End}

\bigskip

\begin{figure}
\pgfdeclareimage[width=0.3\hsize]{brum}{brum2.png}
\pgfuseimage{brum}
\end{figure}

\end{frame}

\end{document}
