NP-completeness, we could safely assume that all the models are equivalent,
possibly up to polynomial slowdown which is negligible. In our case, the
differences between good and not-so-good algorithms are on a~much smaller
-scale. In this chapter, we will replace the usual ``yardsticks'' by a~micrometer,
+scale. In this chapter, we will replace the usual ``tape measure'' by a~micrometer,
state our computation models carefully and develop a repertoire of basic
data structures taking advantage of the fine details of the models.
On the other hand, we are interested in polynomial-time algorithms only, so $\Theta(\log N)$-bit
numbers should be sufficient. In practice, we pick~$W$ to be the larger of
$\Theta(\log N)$ and the size of integers used in the algorithm's input and output.
- We will call an integer which fits in a~single memory cell a~\df{machine word.}
+ We will call an integer that fits in a~single memory cell a~\df{machine word.}
\endlist
Both restrictions easily avoid the problems of unbounded parallelism. The first
standard complexity classes, but the calculations of time and space complexity tend
to be somewhat tedious. What more, when compared with the RAM with restricted
word size, the complexities are usually exactly $\Theta(W)$ times higher.
-This does not hold in general (consider a~program which uses many small numbers
+This does not hold in general (consider a~program that uses many small numbers
and $\O(1)$ large ones), but it is true for the algorithms we are interested in.
Therefore we will always assume that the operations have unit cost and we make
sure that all numbers are limited by the available word size.
%--------------------------------------------------------------------------------
-\section{Bucket sorting and contractions}\id{bucketsort}%
+\section{Bucket sorting and unification}\id{bucketsort}%
-The Contractive Bor\o{u}vka's algorithm (\ref{contbor}) needed to contract a~given
-set of edges in the current graph and flatten it afterwards, all this in time $\O(m)$.
-We have spared the technical details for this section and they will be useful
-in further algorithms, too.
+The Contractive Bor\o{u}vka's algorithm (\ref{contbor}) needs to contract a~given
+set of edges in the current graph and then flatten the graph, all this in time $\O(m)$.
+We have spared the technical details for this section, in which we are going to
+explain several rather general techniques based on bucket sorting.
-As already suggested, the contractions can be performed by building an~auxiliary
-graph and finding its connected components. Thus we will take care of the flattening
-only.
+As we have already suggested in the proof of Lemma \ref{contbor}, contractions
+can be performed in linear time by building an~auxiliary graph and finding its
+connected components. We will thus take care only of the subsequent flattening.
-\para
-On the RAM, it is sufficient to sort the edges lexicographically (each edge viewed
-as an~ordered pair of vertex identifiers with the smaller of the identifiers placed
-first). We can do that by a two-pass bucket sort with~$n$ buckets corresponding
-to the vertex identifiers.
+\paran{Flattening on RAM}%
+On the RAM, we can view the edges as ordered pairs of vertex identifiers with the
+smaller of the identifiers placed first and sort them lexicographically. This brings
+parallel edges together, so that a~simple linear scan suffices to find each bunch
+of parallel edges and remove all but the lightest one.
+Lexicographic sorting of pairs can be accomplished in linear time by a~two-pass
+bucket sort with $n$~buckets corresponding to the vertex identifiers.
However, there is a~catch in this. Suppose that we use the standard representation
of graphs by adjacency lists whose heads are stored in an array indexed by vertex
identifiers. When we contract and flatten the graph, the number of vertices decreases,
but if we inherit the original vertex identifiers, the arrays will still have the
-same size. Hence we spend a~super-linear amount of time on scanning the increasingly
+same size. We could then waste a~super-linear amount of time by scanning the increasingly
sparse arrays, most of the time skipping unused entries.
-To avoid this, we have to renumber the vertices after each contraction to component
-identifiers from the auxiliary graph and we create a~new vertex array. This way,
-the representation of the graph will be kept linear with respect to the size of the
-current graph.
+To avoid this problem, we have to renumber the vertices after each contraction to component
+identifiers from the auxiliary graph and create a~new vertex array. This helps
+keep the size of the representation of the graph linear with respect to its current
+size.
-\para
-The pointer representation of graphs does not suffer from sparsity as the vertices
+\paran{Flattening on PM}%
+The pointer representation of graphs does not suffer from sparsity since the vertices
are always identified by pointers to per-vertex structures. Each such structure
then contains all attributes associated with the vertex, including the head of its
adjacency list. However, we have to find a~way how to perform bucket sorting
-without arrays.
+without indexing of arrays.
+
+We will keep a~list of the per-vertex structures that defines the order of~vertices.
+Each such structure will be endowed with a~pointer to the head of the list of items in
+the corresponding bucket. Inserting an~edge to a~bucket can be then done in constant time
+and scanning the contents of all~$n$ buckets takes $\O(n+m)$ time.
+
+At last, we must not forget that while it was easy to \df{normalize} the pairs on the RAM
+by putting the smaller identifier first, this fails on the PM because we can directly
+compare the identifiers only for equality. We can work around this again by bucket-sorting:
+we sort the multiset $\{ (x,i) \mid \hbox{$x$~occurs in the $i$-th pair} \}$ on~$x$.
+Then we reset all pairs and re-insert the values back in their increasing order.
+This is also $\O(n+m)$.
+
+\paran{Tree isomorphism}%
+Another nice example of pointer-based radix sorting is a~Pointer machine algorithm for
+deciding whether two rooted trees are isomorphic. Let us assume for a~moment that
+the outdegree of each vertex is at most a~fixed constant~$k$. We begin by sorting the subtrees
+of both trees by their depth. This can be accomplished by running depth-first search to calculate
+the depths and bucket-sorting them with $n$~buckets afterwards.
+
+Then we proceed from depth~0 to the maximum depth and for each of them we identify
+the isomorphism equivalence classes of subtrees of that particular depth. We will assign
+unique identifiers all such classes; at most~$n+1$ of them are needed as there are
+$n+1$~subtrees in the tree (including the empty subtree). As the PM does not
+have numbers as a~first-class type, we create a~``\df{yardstick}'' ---a~list
+of $n+1$~distinct items--- and we use pointers to these ``ticks'' as identifiers.
+When we are done, isomorphism of the whole trees can be decided by comparing the
+identifiers assigned to their roots.
+
+Suppose that classes of depths $0,\ldots,d-1$ are already computed and we want
+to identify those of depth~$d$. We will denote their count of~$n_d$. We take
+a~root of every such tree and label it with an~ordered $k$-tuple of identifiers
+of its subtrees; when it has less than $k$ sons, we pad the tuple with empty
+subtrees. Tuples corresponding to isomorphic subtrees are identical up to
+reordering of elements. We therefore sort the codes inside each tuple and then
+sort the tuples, which brings the equivalent tuples together.
+
+The first sort (inside the tuples) would be easy on the RAM, but on the PM we
+have to use the normalization trick mentioned above. The second sort is
+a~straightforward $k$-pass bucket sort.
+
+If we are not careful, a~single sorting pass takes $\O(n_d + n)$ time, because
+while we have only $n_d$~items to sort, we have to scan all $n$~buckets. This can
+be easily avoided if we realize that the order of buckets does not need to be
+fixed --- in every pass, we can use a~completely different order and it still
+does bring the equivalent tuples together. Thus we can keep a~list of buckets
+which are used in the current pass and look only inside these buckets. This way,
+we reduce the time spent in a~single pass to $\O(n_d)$ and the whole algorithm
+takes $\O(\sum_d n_d) = \O(n)$.
+
+Our algorithm can be easily modified for trees with unrestricted degrees.
+We replace the fixed $d$-tuples by general sequences of identifiers. The first
+sort does not need any changes. In the second sort, we proceed from the first
+position to the last one and after each bucket-sorting pass we put aside the sequences
+that have just ended. They are obviously not equivalent to any other sequences.
+The second sort is linear in the sum of the lengths of the sequences, which is
+$n_{d+1}$ for depth~$d$. We can therefore decide isomorphism of the whole trees
+in time $\O(\sum_d (n_d + n_{d+1})) = \O(n)$.
+
+The unification of sequences by bucket sorting will be useful in many
+other situations, so we will state it as a~separate lemma:
+
+\lemman{Sequence unification}\id{suniflemma}%
+Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are
+arbitrary pointers and symbols from a~finite alphabet, to equality classes can
+be performed on the Pointer machine in time $\O(n + \sum_i \vert S_i \vert)$.
+
+\rem
+The first linear-time algorithm that partitions all subtrees to isomorphism equivalence
+classes is probably due to Zemlayachenko \cite{zemlay:treeiso}, but it lacks many
+details. Dinitz et al.~\cite{dinitz:treeiso} have recast this algorithm in modern
+terminology and filled the gaps. Our algorithm is easier to formulate than those,
+because it replaces the need for auxiliary data structures by more elaborate bucket
+sorting.
+
+\paran{Topological graph computations}%
+Many graph algorithms are based on the idea of so called \df{micro/macro decomposition:}
+We decompose a~graph to subgraphs on roughly~$k$ vertices and solve the problem
+separately inside these ``micrographs'' and in the ``macrograph'' obtained by
+contraction of the micrographs. If $k$~is small enough, many of the micrographs
+are isomorphic, so we can compute the result only once for each isomorphism class
+and recycle it for all micrographs in that class. On the other hand, the macrograph
+is roughly $k$~times smaller than the original graph, so we can use a~less efficient
+algorithm and it will still run in linear time with respect to the size of the original
+graph.
+
+This kind of decomposition is traditionally used for trees, especially in the
+algorithms for the Lowest Common Ancestor problem (cf.~Section \ref{verifysect}
+and the survey paper \cite{alstrup:nca}) and for online maintenance of marked ancestors
+(cf.~Alstrup et al.~\cite{alstrup:marked}). Let us take a~glimpse at what happens when
+we decompose a~tree with $k$ set to~$1/4\cdot\log n$. There are at most $2^{2k} = \sqrt n$ non-isomorphic subtrees of size~$k$,
+because each isomorphism class is uniquely determined by the sequence of $2k$~up/down steps
+performed by depth-first search. Suppose that we are able to decompose the input and identify
+the equivalence classes of microtrees in linear time, then solve the problem in time $\O(\poly(k))$ for
+each microtree and finally in $\O(n'\log n')$ for the macrotree of size $n'=n/k$. When we put these pieces
+together, we get an~algorithm for the whole problem which achieves time complexity $\O(n
++ \sqrt{n}\cdot\poly(\log n) + n/\log n\cdot\log(n/\log n)) = \O(n)$.
+
+Decompositions are usually implemented on the RAM, because subgraphs can be easily
+encoded in numbers, which can be then used to index arrays containing the precomputed
+results. As the previous algorithm for subtree isomorphism shows, indexing is not strictly
+required for identifying equivalent microtrees and it can be replaced by bucket
+sorting on the Pointer machine. Buchsbaum et al.~\cite{buchsbaum:verify} have extended
+this technique to general graphs in form of so called topological graph computations.
+Let us define them.
+
+\defn
+A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of its
+vertices and edges can be arbitrary symbols drawn from a~finite alphabet. The output
+of the computation is another labeling of the same graph. This time, the vertices and
+edges can be labeled with not only symbols of the alphabet, but also with pointers to the vertices
+and edges of the input graph, and possibly also with pointers to outside objects.
+A~graph computation is called \df{topological} if it produces isomorphic
+outputs for isomorphic inputs. The isomorphism of course has to preserve not only
+the structure of the graph, but also the labels in the obvious way.
+
+\obs
+The topological graph computations cover a~great variety of graph problems, ranging
+from searching for matchings or Eulerian tours to finding Hamilton circuits.
+The MST problem itself however does not belong to this class, because we do not have any means
+of representing the edge weights as labels, unless of course there is only a~fixed amount
+of possible values.
+
+As in the case of tree decompositions, we would like to identify the equivalent subgraphs
+and process only a~single instance from each equivalence class. The obstacle is that
+graph isomorphism is known to be computationally hard (it is one of the few
+problems that are neither known to lie in~$\rm P$ nor to be $\rm NP$-complete;
+see Arvind and Kurur \cite{arvind:isomorph} for recent results on its complexity).
+We will therefore manage with a~weaker form of equivalence, based on some sort
+of graph encodings:
+
+\defn
+A~\df{canonical encoding} of a~given labeled graph represented by adjancency lists
+is obtained by running the depth-first search on the graph and recording its traces.
+We start with an~empty encoding. When we enter
+a~vertex, we assign an~identifier to it (again using a~yardstick to represent numbers)
+and we append the label of this vertex to the encoding. Then we scan all back edges
+going from this vertex and append the identifiers of their destinations, accompanied
+by the edges' labels. Finally we append a~special terminator to mark the boundary
+between the code of this vertex and its successor.
+
+\obs
+The canonical encoding is well defined in the sense that non-iso\-morphic graphs always
+receive different encodings. Obviously, encodings of isomorphic graphs can differ,
+depending on the order of vertices and also of the adjacency lists. A~graph
+on~$n$ vertices with $m$~edges is assigned an~encoding of length at most $2n+2m$ ---
+for each vertex, we record its label and a~single terminator; edges contribute
+by identifiers and labels. These encodings can be constructed in linear time and
+in the same time we can also create a~graph corresponding to any encoding.
+We will use the encodings for our unification of graphs:
-We will keep a~list of the per-vertex structures which defines the order of~vertices.
-Each such structure will contain a~pointer to the head of the corresponding bucket,
-again stored as a~list. Putting an~edge to a~bucket can be done in constant time then,
-scanning all~$n$ buckets takes $\O(n+m)$ time.
+\defn
+For a~collection~$\C$ of graphs, we define $\vert\C\vert$ as the number of graphs in
+the collection and $\Vert\C\Vert$ as their total size, i.e., $\Vert\C\Vert = \sum_{G\in\C} n(G) + m(G)$.
+
+\lemman{Graph unification}\id{guniflemma}%
+A~collection~$\C$ of labeled graphs can be partitioned into classes which share the same
+canonical encoding in time $\O(\Vert\C\Vert)$ on the Pointer machine.
+
+\proof
+Construct canonical encodings of all the graphs and then apply the Sequence unification lemma
+(\ref{suniflemma}) on them.
+\qed
+
+\para
+When we want to perform a~topological computation on a~collection~$\C$ of graphs
+with $k$~vertices, we first precompute its result for a~collection~$\cal G$ of \df{generic graphs}
+corresponding to all possible canonical encodings on $k$~vertices. Then we use unification to match
+the \df{actual graphs} in~$\C$ to the generic graphs in~$\cal G$. This gives us the following
+theorem:
+
+\thmn{Batched topological computations, Buchsbaum et al.~\cite{buchsbaum:verify}}\id{topothm}%
+Suppose that we have a~topological graph computation~$\cal T$ that can be performed in time
+$T(k)$ for graphs on $k$~vertices. Then we can run~$\cal T$ on a~collection~$\C$
+of labeled graphs on~$k$ vertices in time $\O(\Vert\C\Vert + (k+s)^{k(k+2)}\cdot (T(k)+k^2))$,
+where~$s$ is a~constant depending only on the number of symbols used as vertex/edge labels.
+
+\proof
+A~graph on~$k$ vertices has less than~$k^2/2$ edges, so the canonical encodings of
+all such graphs are shorter than $2k + 2k^2/2 = k(k+2)$. Each element of the encoding
+is either a~vertex identifier, or a~symbol, or a~separator, so it can attain at most $k+s$
+possible values for some fixed~$s$.
+We can therefore enumerate all possible encodings and convert them to a~collection $\cal G$
+of all generic graphs such that $\vert{\cal G}\vert \le (k+s)^{k(k+2)}$ and $\Vert{\cal G}\Vert
+\le \vert{\cal G}\vert \cdot k^2$.
+
+We run the computation on all generic graphs in time $\O(\vert{\cal G}\vert \cdot T(k))$
+and then we use the Unification lemma (\ref{guniflemma}) on the union of the collections
+$\C$ and~$\cal G$ to match the generic graphs with the equivalent actual graphs in~$\C$
+in time $\O(\Vert\C\Vert + \Vert{\cal G}\Vert)$.
+Finally we create a~copy of the generic result for each of the actual graphs.
+If the computation uses pointers to the input vertices in its output, we have to
+redirect them to the actual input vertices, which we can do by associating
+the output vertices that refer to an~input vertex with the corresponding places
+in the encoding of the input graph. This way, the whole output can be generated in time
+$\O(\Vert\C\Vert + \Vert{\cal G}\Vert)$.
+\qed
-\FIXME{Add an example of locally determined orders, e.g., tree isomorphism?}
+\rem
+The topological computations and the Graph unification lemma will play important
+roles in Sections \ref{verifysect} and \ref{optalgsect}.
%--------------------------------------------------------------------------------
\section{Data structures on the RAM}
+\id{ramdssect}
There is a~lot of data structures designed specifically for the RAM, taking
advantage of both indexing and arithmetics. In many cases, they surpass the known
i.e., the smallest~$i$ such that $\alpha[i]=1$.
By a~combination of subtraction with $\bxor$, we create a~number
-which contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
+that contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
\alik{
\alpha&= \9\9\9\9\9\1\0\0\0\0\cr
\endalgo
\rem
-We have used a~plenty of constants which depend on the format of the vectors.
+We have used a~plenty of constants that depend on the format of the vectors.
Either we can write non-uniform programs (see \ref{nonuniform}) and use native constants,
or we can observe that all such constants can be easily manufactured. For example,
$(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1)$. The only exceptions
\proof
There are $2^{\O(k^3)}$ possible combinations of arguments of the given size and for each of
-them we spend $\O(k^c)$ time by calculating the function (for some~$c\ge 1$). It remains
-to observe that $2^{\O(k^3)}\cdot \O(k^c) = \O(2^{k^4})$.
+them we spend $\poly(k)$ time on calculating the function. It remains
+to observe that $2^{\O(k^3)}\cdot \poly(k) = \O(2^{k^4})$.
\qed
\para
where~$\(x)$ disagrees with a~label. Before this point, all edges not taken by
the search were leading either to subtrees containing elements all smaller than~$x$
or all larger than~$x$ and the only values not known yet are those in the subtree
-below the edge which we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
+below the edge that we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
all values in that subtree have $x_j[b]=1$ and thus they are larger than~$x$. In the other
case, $x[b]=1$ and $x_j[b]=0$, so they are smaller.
\qed
must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
right subtree. Both subtrees can be then constructed recursively.\foot{This
construction is also known as the \df{cartesian tree} for the sequence
-$g_1,\ldots,g_n$.}
+$g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be
+built in $\O(n)$ time. A~nice application on the Lowest Common Ancestor
+and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.}
\qed
\para
and we have no upper bound on~$W$ in terms of~$k$), so we will compress it even
further:
-\nota
+\nota\id{qhnota}%
\itemize\ibull
\:$B = \{g_1,\ldots,g_n\}$ --- the set of bit positions of all the guides, stored as a~sorted array,
\:$G : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\}$ --- a~function mapping
for a~newly inserted element in constant time. However, the set is too large
to fit in a~vector and we cannot perform insertion on an~ordinary array in
constant time. This can be worked around by keeping the set in an~unsorted
-array together with a~vector containing the permutation which sorts the array.
+array together with a~vector containing the permutation that sorts the array.
We can then insert a~new element at an~arbitrary place in the array and just
update the permutation to reflect the correct order.
(a~vector of $\O(n\log k)$ bits; we will write $x_i$ for $X[\varrho(i)]$),
\:$B$ --- a~set of ``interesting'' bit positions
(a~sorted vector of~$\O(n\log W)$ bits),
-\:$G$ --- the function which maps the guides to the bit positions in~$B$
+\:$G$ --- the function that maps the guides to the bit positions in~$B$
(a~vector of~$\O(n\log k)$ bits),
\:precomputed tables of various functions.
\endlist
projects / saga.git / blobdiff