Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

We describe a slightly generalized variant of the well-known concept of $r$-divisions sketched in the introduction. We start with a small set of definitions. A balanced separator of a graph $G=(V,E)$ is a set of vertices $S\subset V$ such that each connected component of $G[V\setminus S]$ contains at most a constant fraction of the vertices. The exact constant does not matter to us. We call a class of graphs $𝒢$ that is closed under taking vertex induced subgraphs $O(n^{ϵ})$-separable if there exists a constant $ϵ$ with , such that each $G=(V,E)\in 𝒢$ has a balanced separator $S\subset V$ of size $O(n^{ϵ})$. We simply say that a graph or class of graphs is separable if the size of the balanced separator is of no particular concern to us.

See Figure 1 for a sketch of such a division. The reason we introduce the relaxation $\alpha$, is due to our desire to achieve space-efficiency when algorithmically constructing a division. There exists an algorithm that computes a $(\log n,r)$-relaxed division via recursive separator searches that uses only $O(n)$ bits and, for planar graphs, $O(n)$ time [21]. If the construction step of our encoding must not be space-efficient, one can of course use a standard non-space efficient algorithm [12, 23], and therefore have a relaxation factor of $\alpha =1$; for our application a factor of $\alpha =\log n$ allows for a more (space-)efficient computation of our final encoding, buy when using the encoding makes no difference. Common applications of divisions use them in a recursive fashion, and so do we. In particular, we construct for each piece of some $(\alpha ,r)$-relaxed division a $(1,\tilde{r})$-relaxed division where $\tilde{r}\ll r$. For this, we define a nested division for a separable graph $G$ as follows.

If we have an $(\alpha ,r,\tilde{r})$-nested division for a graph $G$ each vertex can be viewed as being part of three levels:

• $\mathrm{■}$

  graph: Each vertex is part of $V$.

• $\mathrm{■}$

  mini: Each vertex of $V$ is assigned to one or more mini pieces.

• $\mathrm{■}$

  micro: Each vertex of $V$ is assigned to one or more micro pieces.

Given an $(\alpha ,r,\tilde{r})$-nested division for a graph $G$ we can categorize all vertices as follows. We call a vertex mini (micro) boundary if it is a boundary vertex in a mini (micro) piece, and mini (micro) non-boundary if it is not a boundary vertex in a mini (micro) piece. Edges are categorized similarly: an edge is called mini (micro) boundary edge if both endpoints are mini (micro) boundary vertices, mini (micro) non-boundary edge if both endpoints are mini (micro) non-boundary vertices, and mini (micro) transitional edge otherwise. We routinely drop the specifier mini or micro if we make statements that apply to both mini and micro levels. We are interested in bounding the number of total occurrences of mini (micro) boundary vertices among all mini (micro) pieces, referred to as mini (micro) duplicates. Let $𝒫$ be an $(\alpha ,r)$-relaxed division constructed for an $O(n^{ϵ})$-separable graph $G$. As each piece has $O(r^{ϵ})$ boundary vertices, the total number of duplicates is $O((n/r)(\alpha r^{ϵ}))$. Thus, for a nested division we have $O(\alpha n/r^{1-ϵ})$ (duplicates of) mini boundary vertices, and $O((n/r)(r/\tilde{r})({\tilde{r}}^{ϵ}))=O(n/{\tilde{r}}^{1-ϵ})$ (duplicates of) micro boundary vertices. We refer to a more detailed description of the reasoning behind these bounds to Blelloch and Farzan [6]. We summarize it in the following lemma.

For all of our use cases of $(\alpha ,r,\tilde{r})$-nested divisions we have $\alpha =O(\log n)$, $r=\mathrm{poly}(\log n)$ and $\tilde{r}=\mathrm{poly}(\log \log n)$, with the exact polynomial chosen such that we have $O(n/\mathrm{poly}(\log n))$ (duplicates of) mini boundary vertices, and $O(n/\mathrm{poly}(\log \log n))$ (duplicates of) micro boundary vertices. For the remainder of our paper, when we refer to a nested division we refer to a $(\log n,\mathrm{poly}(\log n),\mathrm{poly}(\log \log n))$-nested division.

As we now describe concrete data structures, we fix our model of computation to the word RAM model with word size $\mathrm{\Omega }(\log n)$. For the rest of the section, let $G$ be a separable graph and assume that a nested division is given for $G$. We begin by outlining the most basic functionality we require for a nested division when used as a data structure to encode a graph. Blelloch and Farzan presented a succinct encoding for unlabeled separable graphs that effectively uses a nested division at its core, and the framework we present in this subsection is based on their work [6], defined slightly more general to allow for our later augmentations. While they do not use an $\alpha$-relaxation factor for the initial $(\alpha ,r)$-relaxed division of the nested division (they use their own variation of a standard recursively constructed $r$-division), their framework works with $\alpha =\log n$ without any modifications. Their general idea is to succinctly encode the nested division, and encode each piece at the micro level as an index into a lookup table. Boundary vertices are encoded via additional data structures that use standard non-space efficient techniques, e.g., using arrays and lists. Combined with a succinct bidirectional mapping that maps a vertex to its different occurrences in each level (graph, mini and micro) they realize neighborhood, adjacency and degree queries.

To describe the functionality of these bidirectional mappings, we introduce a labeling of pieces and vertices. Each mini piece $P_i\in 𝒫$ is uniquely identified by an id $i$. Analogously, the relaxed division constructed for each $P_i$ is identified as ${𝒫}_i$. Each micro piece $P_{i,j}$ is identified by a tuple $(i,j)$ with $j$ indicating it is the piece with id $j$, i.e., piece $P_{i,j}\in {𝒫}_i$. Each vertex $u\in V$ has a graph label assigned from $[n]$, a mini label $u_i$ assigned from $[r]$ in each mini piece $P_i$ it is contained, and a micro label assigned from $[\tilde{r}]$ in each micro piece $P_{i,j}$ it is contained. When we talk about a vertex $u\in V$ we always assume that $u$ is identified by its graph label. The mappings that are provided are as follows: given a vertex $u\in V$ output the tuples $(i,u_i)$ such $u_i$ is the mini label of $u$ in the piece $P_i$. Analogously for a given tuple $(i,u_i)$ where $i$ refers to a mini piece $P_i$ and $u_i$ is the label of some vertex of $P_i$, output the tuple $(j,u_{i,j})$ where $u_{i,j}$ is the micro label of vertex $u_i$ in a micro piece $P_{i,j}$. Note that each of these queries can output more than one element if the vertex is a boundary vertex at the respective level. For less verbose writing we implicitly assume that we always have access to all mappings outlined in this paragraph and only make distinctions between the different types of labeling if necessary. We refer to the set of all outlined mappings as translation mappings.

In the following we want to augment the nested division of Lemma 6 with various capabilities. For this we analyze the runtime and memory budget we have when our goal is to run some algorithms in $o(n)$ time and with $o(n)$ bits, followed by outlining necessary techniques. As stated, we construct our nested divisions with $r=\mathrm{poly}(\log n)$, $\tilde{r}=\mathrm{poly}(\log \log n)$ and $\alpha =\log n$. This means that for each of the $O(n/\mathrm{poly}(\log n))$ mini boundary vertices we have a memory budget of $\mathrm{poly}(\log n)$ bits. Analogously, we have a budget of $\mathrm{poly}(\log \log n)$ bits for each of the $O(n/\mathrm{poly}(\log \log n))$ micro-boundary vertices. This means, we have a budget of $\mathrm{poly}(\log n)$ bits for each mini piece and $\mathrm{poly}(\log \log n)$ for each micro piece. These bounds allow us to use more space than what is needed for our applications, as we only require $O(\log n)$ bits per mini boundary vertex (and mini piece), and $O(\log \log n)$ bits per micro boundary vertex (and micro piece) for our applications. We have the same budget for the runtime as we do for memory, but for our application only require (amortized) constant time per boundary vertex.

For micro pieces we use a table lookup technique for constant time computations to subproblems. Micro pieces are so tiny, that any query we require can be described by a constant number of words in the word RAM model. We assume that we have a lookup table available that lists all graphs with at most $\tilde{r}$ vertices of the separable graph class $𝒢$ we work with. The table lists all graphs modulo isomorphism, i.e., no two entries are isomorphic. This is not enough for us, as we require additional data for the boundary vertices. Instead, we require the graphs of the lookup table to be partially augmented, meaning for at most $b=O({\tilde{r}}^{ϵ})$ vertices of each graph $G^{\prime }$ of the lookup table we store a bit string (called a partial vertex augmentation) of some fixed length $\mathrm{\ell }=O(\log \tilde{r})$, and an additional bitstring of length $O(b\mathrm{\ell })$ (called a partial graph augmentation).

Using a lookup table that lists all partially augmented graphs with at most $\tilde{r}$ vertices, we can realize what we refer to as swapping indices. Each micro piece is encoded as an index into the lookup table referencing some graph $G^{\prime }$ together with its partial augmentations. When we want to update values stored for (the micro boundary vertices of) the micro piece we concretely do this by changing the index we store. Let $P_{i,j}$ be some micro piece encoded as an index $x$ into the lookup table. To update an augmented value in the micro piece, e.g., color a boundary vertex, we can replace the index $x$ with a different index $y$. See Figure 2 for an example. We have to take care while constructing the table that any changes of the partial augmentation (i.e., the values stored for boundary vertices) does not change the internal labels of the graph, i.e., the names of the vertices stay the same independent of the changes we make to the data stored for boundary vertices. For the rest of our paper we always assume that we have access to such a lookup table.

In addition to the standard stack-based approach for implementing a DFS, there is also an iterator approach that stores for each vertex an iterator of the adjacency list. We implement the second variant. Let $T$ be the palm tree constructed by some DFS traversal. See Figure 3 for an example of the following description. We say $T$ enters a piece $P$ if the there exists tree edges $(u,v)$ and $(v,w)$ with only the edge $\{v,w\}$ part of the piece $P$, or if edge $\{v,w\}$ is part of the piece $P$, $(v,w)$ is a tree edge, and $v$ is the root of $T$. We then call $v$ an entry vertex of $P$. Furthermore, we say $T$ exits $P$ if there exist tree edges $(u,v)$ and $(v,w)$ with only $\{u,v\}$ part of $P$ and $\{v,w\}$ not part of $P$. We then call $v$ an exit vertex of $P$. We say $T$ starts at a piece $P$ if the tree edge $(u,v)$ exists with $u$ the root of $T$, $v$ is the first vertex visited after $u$ and $\{u,v\}$ is part of $P$. Note that the entry of a piece is by definition a boundary vertex of some piece $P$, or the root of $T$. For us there is no difference between the two cases of entry vertex (i.e., boundary vertex or root). We refer to an exit vertex together with its matching entry vertex as an entry-exit pair. For easier description we refer to an entry vertex that has no matching exit vertex as part of an entry-exit pair where the entry is mapped to some special symbol, called the null exit. The following observation directly follows.

Let $P$ be some micro piece stored as an index to the lookup table. We define a partial DFS state of $P$ as a coloring of the vertices of $P$ with the colors unvisited (white), currently visited (gray) and finished (black), and a constant number of (possibly empty) ordered sets of entry-exit pairs, ordered by, e.g., the pre-/and post-order numbering of their respective entry vertex, with ties being broken arbitrarily.
By the capabilities of the table lookup outlined in the previous section, an index of the lookup table is able to encode this information. The idea is that, when the DFS enters a micro piece $P$, categorized by some index $x$ of the lookup table encoding $P$ together with its partial DFS state, we obtain in $O(1)$ time an index $y$ of the lookup table encoding $P$ together with the next partial DFS state. We then swap out the index $x$ with the index $y$. Note that this query depends on: the piece $P$, the coloring of the vertices of $P$, the ordered set of entry-exit pairs and the vertex we used to just enter the piece $P$ (or the vertex we just backtracked to). This information is enough to obtain a new DFS state that correctly advances the DFS through $P$ while considering the current partial DFS state. Since such an advancement results in the DFS traversing up to (or backtracking to) the next micro boundary vertex we obtain a new entry-exit pair in $O(1)$ time. There are multiple possible viable partial DFS states that one could obtain by this operation, but we store one fixed state per entry of the lookup table, which is all that we require. See Figure 3 again for a visualization of how the DFS progresses through a piece. The change from one state of the figure to the next is done in $O(1)$ time for micro pieces.
A final note considers marking vertices as gray or black in micro pieces. When we visit a micro boundary vertex $u$, we must color $u$ in all micro pieces $P_{i,j}$ that contain $u$ (as micro label $u_{i,j}$). The translation mappings allow us to iterate over all micro pieces that contain $u_{i,j}$ in constant time per element output. For each such element output we must switch out the respective index of the micro pieces via the lookup table. This is done exactly twice (white to gray, and gray to black) per duplicate of a micro boundary vertices, and thus the time is linear in the number of total micro boundary vertices.
We now describe the data structures required for implementing the DFS. We begin with a description of how to implement an iterator over the neighborhood that can be paused and resumed. Note that while the nested division $𝒟$ provides neighborhood iteration (Lemma 6), it is not assumed that this iteration can be paused and continued at a later point in time without starting the process from the beginning. First, we describe this process for micro boundary vertices $u_i$ in some piece $P_i$. For each such $u_i$ store an array $A$ containing the indices of each micro piece $P_{i,j}$ that contains $u_i$ (as micro label $u_{i,j}$). An iterator for $u_i$ now consists of an index $j$ of $A$ together with an index into the adjacency array of $u_{i,j}$ in $P_{i,j}$. Note that the array $A$ contains many entries for each micro boundary vertex. By Lemma 5 this is asymptotically no problem, as the number of entries in all arrays $A$ depends linearly on the number of micro boundary vertices. The arrays $A$ can be built in sublinear time and space by iterating over all micro pieces, and inside each micro piece iterating over all micro-boundary vertices. We store the analogous data structure for all mini boundary vertices. We now must store the state of each iterator during the DFS. Construct an array storing for each boundary vertex the state of the iterator over $u$’s neighborhood together with $u$’s parent in the DFS tree and the color visited/unvisited. This uses $O(\log n)$ bits per mini boundary vertex. For each mini piece $P_i$ we construct arrays storing the respective information of micro boundary vertices. As each vertex $u$ (identified via mini label $u_i$) in $P_i$ has a degree of $O(r)$ and must have its parent in $P_i$ (identified by some mini label $v_i\in [r]$), this information can be stored with $O(\log r)=O(\log \log n)$ bits per micro boundary vertex. All other vertices are handled by the lookup table. All other data structures use $o(n)$ bits.

The DFS naturally computes the palm tree, but it remains to show how to store it such that afterward we can execute common queries such as iteration over all children (i.e., incident tree edges), or iteration over all back edges that start/end at a given vertex. We describe this for iteration over all children of a vertex, the other queries are realized in the exact same fashion. For micro non-boundary vertices these queries can directly be provided by the table lookup, or by recursive structure. We thus focus on the boundary vertices. For each mini boundary vertex $u$ we maintain a list $L$ containing the ids of all mini pieces $P$ such that $u$ has a child in $P$. Iteration over the children of $u$ can then be expressed as an iteration over $L$, and for each $i\in L$ we output all children of $u$ in $P_i$. Concretely this is done by outputting all children of $u_i$ (the mini label of $u$ in $P_i$) as their respective mini labels, and then translating them to their global labels. For micro boundary vertices, analogous structures are built. The space analysis is analogous to the space analysis of the previous paragraph, i.e., it uses $o(n)$ bits total. We summarize the results in the next lemma.

During the computation of a DFS it is common to store various values that relate to the traversal such as the pre-order $\mathrm{pre}(u)$ of a vertex $u$, or more complex values such as the lowpoint of a vertex $u$, defined as the lowest numbered (by pre-order numbering) vertex reachable via a path starting at $u$ that consists of zero or more tree edges and at most one back edge. We can augment $𝒟$ with this information as follows. We start to describe the computation of the pre-ordering number $\mathrm{pre}(u)$. Post-order can be implemented in an analogous way. Assume that we have constructed the palm tree of Lemma 8.

For planar graphs we can construct the encoding of Lemma 6 efficiently, both in time and space. Kammer and Meintrup [21] presented a space-efficient algorithm for computing a $(\log n,r)$-relaxed divisions of minor closed graph classes that roughly works as follows. The input graph $G$ is replaced with a minor $F$ that contains $O(n/\log n)$ vertices such that each vertex of $F$ represents $\mathrm{\Theta }(\log n)$ vertices of $G$. Then, any algorithm $𝒜$ can be used for computing an $(1,r)$-relaxed division (a standard $r$-division) of $F$, which then can be turned into a $(\log n,r)$-relaxed division of $G$. As $𝒜$ is executed on a graph with $O(n/\log n)$ vertices, we achieve a speedup of a factor of $\mathrm{\Theta }(\log n)$, and a space reduction by the same factor. Translation between the graph $F$ and $G$ uses linear time and bits. When recursively constructing divisions of mini pieces we can use standard algorithms as the graphs are small enough. For planar graphs, linear time $r$-division algorithms [12, 23] exist, and thus the entire computation of the recursive division runs in linear time. For other graph classes the runtime depends on how efficiently separators can be found.

The final non-trivial part of constructing our encoding are related to the translation mappings between the different levels. The mapping is constructed using the powerful fully-indexable dictionary (FID) of Raman et al. [26] that, for a given universe $[\mathrm{\ell }]$, uses $o(\mathrm{\ell })$ bits total when managing a set $S\subset [\mathrm{\ell }]$ with $|S|=\mathrm{\Theta }(\mathrm{\ell }/\mathrm{poly}(\log \mathrm{\ell }))$, which fits Blelloch and Farzan’s use case. Effectively, this FID manages a compressed bit vector $B$ of length $\mathrm{\ell }$ where in $B$ bits at index $i\in S$ are set to $1$. Due to the use of Raman et al.’s FID their construction takes polynomial time $\omega (n)$ even for the simple case of encoding planar graphs and without regard to space-efficiency during the construction step. While Raman et al. mention their data structure can be constructed in expected linear time, a deterministic linear time construction is not known. This is due to the use of a certain hash function that is required. When succinctness is not required much simpler dictionaries suffices for the translation mappings. In this case, we effectively follow the same techniques outlined by Blelloch and Farzan, but use the indexable dictionary of Baumann and Hagerup, which can be constructed in $O(\mathrm{\ell }/\log \mathrm{\ell })$ time and uses $\mathrm{\ell }+o(\mathrm{\ell })$ bits for managing any set $S\subset [\mathrm{\ell }]$:

Using the FID of Lemma 10 we are able to construct a compact variant of the encoding of Lemma 6 in $O(n)$ time and bits. If one is fine with expected linear time, the FID of Raman et al. [26] can be used and the encoding remains succinct. The functionalities of the different variants are the same.

Combining Corollary 11 with Theorem 1 we are able to show Corollary 2. We give a more general version for arbitrary separable graphs next. In the following we denote with $f_{𝒢}(n)$ the runtime of an algorithm for graphs with $n$ vertices of some separable graph class $𝒢$ that recursively computes a balanced separator until the graphs are small enough (of poly-logarithmic size), and with $f_{𝒢}^{\prime }(n)$ the number of bits required by such an algorithm.