Linear-Time In-Place DFS and BFS in the
Restore Model
Frank Kammer and Andrej Sajenko

arXiv:1803.04282v1 [cs.DS] 12 Mar 2018

THM, University of Applied Sciences Mittelhessen, Germany
{frank.kammer,andrej.sajenko}@mni.thm.de

Abstract We present an in-place depth first search (DFS) and an inplace breadth first search (BFS) that runs in the restore model in linear
time. To obtain our results we show several linear-time in-place graph
transformations from one representation to another representation.
Keywords space efficient, depth first search, breadth first search, cross
pointer, restore model

1

Introduction

Because of the rapid growth of the data sizes in nowadays applications, algorithms that are designed to efficiently utilize space are becoming more and more
important. Another reason for the need for such algorithms is the limitation in
the memory sizes of tiniest devices.
Several models of computation have been considered for the case when writing in the input area is restricted. In the multi-pass streaming model [17] the
input is assumed to be held in a read-only sequentially-accessible media, and
the main optimization target is the number of passes an algorithm makes over
the input. In the read-only word RAM [13] the input is assumed to be stored on
a read-only randomly-accessible media, and arithmetic operations on operands
that fit in a computer word are assumed to take constant time each. Another
model allows the input to be permuted but not destroyed [5]. A variant of the
latter model is called the restore model [8] where the input array is allowed to
be modified during the process of answering a query, but it has to be restored
to its original state afterwards.
There are several algorithms for the read-only word RAM, e.g., for sorting [4,18], geometric problems [1,3,12], or graph algorithms [2,7,9,11,14,15,16].
Unfortunately, there is not much hope to find an in-place graph algorithm—i.e.,
an algorithm on graphs that uses only O(1) extra words—in the read-only RAM
model since there is a lower bound for the reachability problem [10], i.e., the problem to find out if two given vertices of a given graph are in the same connected
component. The lower bound essentially says that we can solve reachability in
polynomial time only if we have roughly Θ(n) bits of working memory.
Therefore, we focus on a different model: the restore model on a word RAM
where we assume that the word size is at least ⌈log2 (N )⌉ with N being is the
1

size of the input. We are not aware of an in-place DFS of BFS in this model.
However, Chakraborty et al. [6] introduced another model where the adjacency
arrays of a graph can be only rotated, but a restoration is not required. In their
model, they recently showed that one can run an in-place depth first search
(DFS) and a breath first search (BFS) in O(nℓ2 + m) time if the graph has n
vertices, m edges and if the algorithm constructs a DFS/BFS tree of height ℓ.
They use a graph representation consisting of n + 4m + 2 words.

1.1

Our contribution

We use the restore model to show linear-time in-place algorithms for both DFS
and BFS that runs on a graph with a representation consisting of only n + m + 2
words on directed graphs and n + 2m + 2 words on undirected graphs (each
undirected edge occurs with both endpoints) where n is the number of vertices
and m the number of edges of the graph.
To show our results we use different representations of the graph that all
need the same number of words. We start to show that we can change the
representations with a linear-time in-place algorithm.

2

Representation

Graph algorithms usually do not specify the input format of a given graph since
linear time and a linear number of words of working memory are usually sufficient to convert between any two reasonable adjacency-list representations—e.g.,
reorder the adjacency arrays with radix sort.
However, having only o(n log n) bits of working memory, we have to be more
specific about the input format and also the transformation from one input
format to another is not trivial. In our standard representation (Fig. 1), we first
store the number n of vertices and a table of pointers with one entry for each
vertex. Subsequently, we store the total size of the adjacency arrays. In addition,
we assume that the adjacency array of vertex i is stored before the adjacency
array of vertex i + 1 for all i = 1, . . . , n − 1 and that all vertices inside an
adjacency array are also stored in ascending order.
Another representation is the cross-pointer representation (Fig. 2), which is
identical to the standard representation except that the adjacency arrays store
pointers to the cross-edges instead of vertex names. In other words, a word
storing a vertex v in the adjacency array of a vertex u is replaced by the pointer to
the word storing u in the adjacency array of v. The cross-pointer representation
is useful for many space-efficient graph algorithms [11,15,16].
Moreover, we introduce in this paper the adjacency-array begin-pointer representation or short the begin-pointer representation (Fig. 3). We obtain the
representation by replacing each vertex name v in the standard representation
by a pointer to the beginning of the adjacency-array of vertex v.
2

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

5

7

9

12

14

17

12

2

5

1

3

4

2

4

2

3

5

1

4

n

2m

T

Figure 1: Standard representation of a graph with m undirected or 2m directed
edges.

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

5

7

9

12

14

17

12

9

17

7

12

14

10

15

11

13

18

8

16

n

2m

T

Figure 2. Cross-pointer representation of the graph from Figure 1.

A

0

1

2

3

4

5

5

7

9

12

14

17

n

T

6

7

8

9

10

11 12 13 14 15

16 17 18

12

9

17

7

12

14

17

9

14

9

12

7

14

2m

Figure 3. Begin-pointer representation of the graph from Figure 1.

3
3.1

Transformations of our Representations
Cross-Pointer and Begin-Pointer Representation

To compute the cross-pointer representation, the idea is to store some information in the table T of pointers that helps our algorithm, but allows us finally
to restore the table. For our algorithm, we use the invariant that the pointer
T [v] of each vertex v in the table T points to the first neighbor of v in the adjacency array that is not yet replaced. The invariant is true in the beginning of
the algorithm.
We consider the vertices v in increasing order and iterate through the neighbors in their adjacency arrays also in increasing order. We replace the vertex
names with the positions of their corresponding cross-edges as follows. The replacement takes a vertex u at a position pu and lookup the position pv = T [u] of
vertex v in the adjacency array of u. By the invariant, T [u] points to the smallest
neighbor of u that has not been replaced yet in u’s adjacency array, and this
neighbor is exactly v. Now we replace the vertex names with the position of its
corresponding edge, i.e., set A[pu ] = pv , A[pv ] = pu .
To reestablish the invariant again, we increment T [v] and T [u]. Afterwards,
we check if T [v] points at a word > n or if T [u] = T [u + 1]. If both check passes,
continue with the next vertex in the adjacency array of v. Otherwise, we reached
the end of v’s adjacency array and we proceed with vertex v + 1 unless v = n.
To start with vertex v + 1, we start with the vertex in A[T [v + 1]].
3

After this process, each pointer T [v] points to the word behind the end of v’s
adjacency array, which is the beginning of the next adjacency array. Therefore,
we can restore the pointers in T by using the previous vertex pointer and set
T [v] := T [v − 1] for v = n, . . . , 2. Finally set T [1] := n + 2.
Lemma 1. There is an in-place transformation from the standard representation to the cross-pointer representation that runs in linear time.
The begin-pointer representation can be computed very easily. Iterate over
all adjacency arrays and replace each entry A[i] := T [A[i]].
Lemma 2. There is an in-place transformation from the standard representation to the begin-pointer representation that runs in linear time.
3.2

Restoring the Standard Representation

The goal is now to replace the pointers with the vertex name of the adjacency
array they point into. To find out the vertex name of an adjacency array we
write the vertex name into the first position of its adjacency array. Since we do
not want to lose the values stored there, we move them temporally inside T .
Of course, we lose the pointers stored there, but we can reconstruct them by
knowing the positions where the vertex names are stored. Because the vertex
names are lower than a cross-pointer, we are still able to distinguish between
them and to notice whenever an adjacency array ends and a new begins.
We call a cross-pointer or a begin-pointer representation swapped whenever
each adjacency array has a vertex name and T [u] stores an information that is
usually part of u’s adjacency array. For examples, see Fig. 4 and 5. Clearly, we
can change a representation into a swapped one by iterating once through T .
For the reverse direction, we have to iterate over all adjacency arrays to find the
vertex names and write their positions into T .
Lemma 3. There is an in-place transformation that swaps and unswaps a representation in linear time.
For a simpler description of the algorithm we assume that an access to the
adjacency array always returns a pointer and Name[p] returns the vertex name
if it is stored in A[p]. Moreover, if we say that we store a vertex name v in A
or store v at some position of some adjacency array, then we mean that the
value from there is moved to T [v] first and subsequently v is stored. Formally,
we distinguish between the raw access to A storing the real data and an access
via A[i] with reading and writing in A[i] means reading and writing in A[i] if and
only if A[i] = 0 or A[i] > n, otherwise the access is to T [A[i]]. In addition, we
have Name[i] = A[i] if and only if A[i] 6= 0 and A[i] ≤ n, otherwise it is null.
In our example shown in Fig. 4, we have A[7] = 9, A[9] = 7 and Name[7] = 1.
To compute the standard representation from a swapped begin-pointer representation is easy. If the given representation is not swapped, then make it
swapped. Iterate then over all adjacency arrays and store in each entry A[i] the
vertex name Name[A[i]]. Finally, unswap the representation.
4

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

5

9

7

10

11

8

12

1

17

2

12

14

3

15

4

13

18

5

16

n

2m

T

Figure 4. Swapped cross-pointer representation of the graph in Fig. 1.

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

5

9

7

9

9

7

12

1

17

2

12

14

3

14

4

12

17

5

14

n

T

2m

Figure 5. Swapped begin-pointer representation of the graph in Fig. 1.

Lemma 4. There is an in-place transformation from the begin-pointer representation to the standard representation that runs in linear time.
To compute the standard representation from a swapped cross-pointer representation, we use an invariant similar to the one used in the previous subsection.
The vertex name is stored in the first word of an adjacency array that has not
yet been replaced by a vertex name. The invariant is true in the beginning of
the algorithm.
We iterate over all pointers in all adjacency arrays in increasing order with
respect to the stored position in A. While considering position q in the adjacency
array of a vertex v we replace the pointer p = A[q] as follows. Determine the
vertex name u of the adjacency array to which p points. By the invariant, u =
A[p]. Set A[q] = u and A[p] = v. Store the vertex names of v and u in A[q + 1]
and A[p + 1], respectively. Thus, the invariant holds again.
After moving the vertex names, check if A[q + 1] > n. If so, continue with
the next pointer in the adjacency array of v. Otherwise, we reached the end of
v’s adjacency array. Then skip over all words smaller than n (these words are
already replaced by vertex names) until reaching the end of A or finding in A
an entry v + 1, which is the position in A of the first not-converted pointer in
(v + 1)’s adjacency array.
Lemma 5. There is an in-place transformation from the cross-pointer representation to the standard representation that runs in linear time.

4

Depth-First Search

As usual, we extend our DFS by the calls of user implemented functions as follows. Initially all vertices of a graph are unvisited, also called white. Whenever
a DFS visits a vertex v for the first time, we call visit(v). Within this call, we
color v gray and execute preprocess(v). Then we iterate over all outgoing edges
5

of v. Whenever the other endpoint u of such an edge is white we call preexplore(v, u). If u turns black and we backtrack to v, we run postexplore(v, u).
When finally everything is explored from v, we call postprocess(v) and color
v black. Using suitable implementations for the four function, we can easily output, e.g., the vertices in pre-, post-, or inorder with respect to our constructed
DFS tree.
4.1

DFS on Directed Graphs

To run our DFS on directed graphs, we use the swapped begin-pointer representation. To run an in-place DFS, we need to know the colors of the vertices
and, if a vertex turns black, the vertex where we have to backtrack. To store
the information, we assume for the time being that every vertex has at least two
edges. Let s be the start vertex of our DFS.
Note that, in the swapped begin-pointer representation, every pointer in an
adjacency array points to a word with a value at most n. Our invariant of our
algorithm is that a vertex v is white if and only if v 6= s and the second entry in
the adjacency array points to a word with a value at most n. Thus, the invariant
is initially true. Note also that the invariant allows us to test in constant time if
a vertex is white.
Assume that our DFS currently visits vertex u and we iterate through u’s
adjacency array. We check for each neighbor v of u if it is white. If so, we visit
v. Let p be the position of the pointer to v’s adjacency array in u’s adjacency
array. Then, v’s adjacency array begins at position q = A[p]. To visit u, the idea
is to set A[p] = A[q + 1] and A[q + 1] = p. Note that the second entry A[q + 1]
of v’s adjacency array now points into u’s adjacency array and is thus a value
larger n. By the setting we additionally have the information to backtrack from
v to u since A[q + 1] is the pointer to the position in u’s adjacency array such
that we can continue our iteration for u.
However, there is a technical issue one has to take care of. By the definition
of A, if a vertex w is discovered from the pointer x at the first position q in v’s
adjacency array, then storing something in A[q] means that we write it to the
table T [v]. Moreover, the reverse pointer in v’s adjacency array can not point
to q (or our invariant would be false). Instead we point to q + 1. Furthermore,
if a vertex w′ is discovered from the second pointer p in v’s adjacency array,
then we can not use the second position in the array to store a pointer from
x′ —otherwise we would loose the pointer used to backtrack from v. Therefore,
the idea is, after returning from w, to swap the pointer w and w′ in v’s adjacency
array and to explore again the first pointer in the array. Whenever we return
from a vertex to the second position of an adjacency array, we have to check
additionally if the first two pointers in the adjacency array are swapped. If so,
we undo the swap and continue with the third pointer in the array. Otherwise,
swap as described above. For an illustration of the algorithm, see Fig. 6.
Before we present the details of our algorithm, let us simplify its description.
We define A∗ [i] as a redirection to A[i] exactly if i is not the second entry of
an adjacency array or if the second entry still points to the beginning of an
6

p

q

q

v

p

q

′

v

p

q

′

v

p

q

′

v

p

q

x

v

p

q

x

v

. . . backtrack and swap x and x′p
v

q

v
x
visit v

u

v
x

visit w

u

v
z

u

. . . backtrack
v
x
swap x and x
v

u

u

v

z′

x

u

u

visit w′′
v
x

u

. . . backtrack from w′′
v
x

u

. . . backtrack from v
v
x

x

x

x

x

′′

w

x

′′

w

x

′′

w q+1

x

′′

w z+1

x
p

z

x
p

x
p

′

x′
visit w′

x

x
′

u

x′
p

x′′

z′

x′
p

x′′

w′ q+1
x′′

p

x′

v

p

q

x′

v

p

q

′

v

p

q

q

v x′ +1 x′′

x

w′

x′′

w′′ z ′′
x′′

p

z ′′

w′′ q+2

p

x′′

w′′ z ′′ +1

Figure 6: Animation of our DFS on directed graph visiting vertices u, v, x, return
to v, visit x′ , return to v, visit x′′ , return to v and return to u.

adjacency array, i.e, (Name[i − 1] = null) ∨ (0 < A[i] ≤ n). Otherwise, p = A[i]
is a back pointer to a parent into a position where the actual edge is stored.
Because we never point to the first position inside an adjacency array, we have
to run an extra check if p points to the second position (Name[p − 1] 6= null).
In this case we find our value at the first position and accesses to A∗ [i] must be
redirected to A[p − 1] = A[A[i] − 1]. Otherwise, A∗ [i] redirects to A[p] = A[A[i]].
7

In detail, our DFS runs as follows. Starting with a vertex v init we search for
the vertex in O(m) time, i.e., search for the position p with A[p] = v init . Then
we call visit(p).
– visit(p): (Visit the vertex whose adjacency array starts at position p.) In
the swapped begin pointer representation, v = Name[p] is always the vertex
name. First, preprocess(v). Finally, start iterating through the neighbors
starting from position p by executing nextNeighbor(p), but skipping over
the first check.
– nextNeighbor(p): (Follows the edge at position p in A∗ if the opposite
endpoint of the edge is white. Otherwise iterate to the next position p + 1.)
First, we check if the edge belongs to the same adjacency array, i.e., check if
Name[p] = null. If not, we reached the next adjacency array and we return
to the parent by lookup the largest q ≤ p such that Name[q] 6= null and
by calling gotoParent(q). Second, we check if the edge at p points to a
white vertex and run the non-recursive procedure isWhite(A∗ [p])=true. If
so, call gotoChild(p). Otherwise, call nextNeighbor(p + 1) again.
– isWhite(p): (Return true exactly if the vertex v whose adjacency array
begins at position p is white.) Recall that we have to check if the second
word of v’s adjacency array points to a value > n. Consequently, return
A[A[p + 1]] > n.
– gotoChild(p): (We are going to discover a new child via an edge e stored
at position p and color it implicitly gray.) First we determine the position
q = A∗ [p] where e points to. Second we get the name of the neighbor v =
Name[q]. Third, we are going to create a pointer to backtrack later and
replace the edge to v with the second edge of v’s adjacency array. Therefore,
remember the second edge x = A[q + 1] of v. Now, store the edge inside
A∗ [p] := x and create a back pointer from v’s second word into its parent’s
adjacency array as follows: Set A[q + 1] := p + 1 if and only if p is the
first position inside the parent’s adjacency array, i.e, if Name[p] 6= null.
Otherwise set A[q +1] := p. Finally, visit the neighbor by executing visit(q).
– gotoParent(q): (From a child v go to its parent where q is the beginning
of v’s adjacency array and p = A[q + 1] is a pointer to the adjacency array of
the parent.) Before going to the parent we have to restore the edges that we
modified when we went to the child. Thus, we first restore the child’s edge
that was temporary stored in the parent’s adjacency array, but let it point
one edge further to guarantee the invariant. In detail, we set A[q + 1] :=
A[p] + 1. Then we restore the pointer to the child by setting A[p] := q.
It remain to check the technical issue described above. For this, check if p
points at the second position of the array, i.e, check if Name[p − 1] 6= null.
If not, call nextNeighbor(p + 1). If the check is true, we have to check
if we left the parent over the first or the second edge. Therefore, check if
the first two words inside the parent’s adjacency array are swapped, i.e,
check if A∗ [p − 1] < A∗ [p]. If so, we left over the first edge of the parent.
Thus, swap A∗ [p − 1] and A∗ [p] and call nextNeighbor(p). Otherwise we
left over the second edge and we swap A∗ [p − 1] and A∗ [p] back and call
nextNeighbor(p + 1).
8

– findNextStartVertex: To check for another unvisited vertex we iterate
through all adjacency arrays by using a global variable. If the invariant fails
for a vertex v whose adjacency array starts at position p, run visit(p).
It remains to describe what we have to do for vertices of degree smaller than 2.
If such a vertex is a start vertex, store the information in a global variable so
that we do not need a second entry in the adjacency array. In addition, whenever
we reach a vertex v of degree 1, then we will neither proceed from v to any other
vertex nor reach v from another vertex again. We therefore need no manipulation
of v’s adjacency array. As a consequence, we can redefine our invariant such that
vertices of degree smaller than 2 are excluded from the invariant.
Finally note that ignoring the calls for the user-defined functions as well as
isWhite, which is not recursive, and findNextStartVertex we only make
tail-calls and consequently require no recursion stack.
Theorem 6. There is a in-place DFS for directed graphs in the restore model
that runs in O(n+m) time on n-vertex m-edge graphs with a representation consisting of n + m + 2 words and that calls the user defined functions preprocess
and postprocess.
Of course, the algorithm above can also run on an undirected graph. However,
on such graphs, we can also call the user defined functions preexplore and
postexplore as we see in the next section.
4.2

DFS on Undirected Graphs

To run our DFS on undirected graphs, we use the swapped cross-pointer representation. The DFS works as follows. Whenever we use a cross-pointer to move
to a new vertex by calling visit(q), we jump into the middle at position q of an
adjacency array of a white vertex. From there, we search for the vertex name
v. Recall that we find the name at the first position of the adjacency array. We
then call preprocess(v). In addition, replace all cross-edges of v’s edges by zero
(avoid so visits of v from descendants of v) and all zero entries at v’s adjacency
array by n + 1 (avoid so visits of v from proper ancestors of v’s parent).
Then we iterate over all non-zero pointers p starting from position q+1 to the
last pointer in v’s adjacency array, then jumping to the first pointer until we reach
position q − 1. Note that we can easily test if we reached the end of v’s adjacency
array by reading the value v + 1 in A, which is the name of the next vertex.
For each such pointer p, restore the cross edge at position p (so that we
can backtrack later), determine the new vertex name as described above and
call preexplore(v, u). Moreover, set A[p] = v so that we know v’s name when
returning to v. Then, call visit(p). The call returns the position p such that
our current visit of vertex v does not need to store p explicitly. Reading A[p],
we relearn the name of v and call postexplore(u, v). Then we step to the
next non-zero pointer in v’s adjacency array unless we reach position q with
0 < A[q] ≤ n. If we reach q, we can backtrack and inform the previous vertex
that we used the edge at position q. Fig. 7 and 8 sketch two snapshots of a DFS.
9

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

5

0

7

0

0

8

12

1

17

2

12

14

3

15

4

13

18

5

16

n

2m

T

Figure 7. A DFS starts at vertex 2.

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

5

9

2

6

6

8

12

1

1

2

12

14

3

0

4

13

18

5

5

n

T

2m

Figure 8: The DFS continues from Fig. 7 and visits vertices 2,1,5 and 4 in this
order.
To start our algorithm below, we can either call findNextComponent to
output all DFS trees or one can output only the vertices of one DFS tree with
start vertex by storing the start vertex in a global variable s and calling visit(q)
where q is the first position in the adjacency array of s.
– visit(q): (Visit a vertex v via an edge that is in v’s adjacency array at
position q.) First, compute the boundaries of the adjacency array containing
A[q], i.e, determine the largest a ≤ q and the smallest b ≥ q with Name[a] 6=
null and Name[b] 6= null. Then, v = Name[a] is our vertex name and we
call preprocess(v) and exit.
Second, eliminate the possibility to visit v again by iterating over p ∈
[a, b]/{q}, replace all A[p] = 0 by A[p] = n + 1, check if there is a crosspointer stored in A[p] > n and destroy it with A[A[p]] := 0.
Finally, start iterating through the neighbors starting from position q + 1 by
calling nextNeighbor(v, q + 1).
– nextNeighbor(v, p): (Finds the next unvisited neighbor and visit it using
v as the name of the current vertex and p is the current position in A.)
First, check if A[p] belongs to v’s adjacency array, i.e., check Name[p] 6=
v + 1. If not, iterate to the largest position q < p such that Name[q] = v
and set p := q.
Second, check if A[p] contains the back edge to the parent of v, i.e, check
if A[A[p]] ≤ n. Also check if Name[p] = s = v, i.e, check if we currently
finished the start vertex. If one of the two checks succeeds, all neighbors of
v are visited and we return by exiting and calling gotoParent(v, p).
If A[p] = 0 or A[p] = n + 1, A[p] initially stored a back or forward edge,
respectively, and we can ignore it, i.e, call nextNeighbor(v, p + 1).
Otherwise, A[p] is a pointer to an unexplored adjacency array. Peek inside
this adjacency array at position A[p] and iterate back using a pointer q until
finding the vertex name u = Name[q] 6= null. Then, call preexplore(v, u)
and explore u by calling gotoChild(v, p).
10

– gotoChild(v, p): (We are going to discover a new child of vertex v via an
edge e stored at position p.) Restore the cross edge e′ of e so that the child
gets a pointer to the edge e by setting A[A[p]] = p. Remember the position
of edge e′ in q = A[p] and write the vertex name v at A[p] such that we can
quickly find out the name of the parent of the child when returning to the
parent. Visit the child by calling visit(q).
– gotoParent(v, p): (Go to the parent of vertex v using the pointer stored
at position p) Go to the parent at the position q = A[p], remember the
vertex name of the parent u = A[q], set A[q] = p and A[p] = 0 to restore
the edge to the child and destroy the back-edge of the child. Call postexplore(v, u) and continue handling the remaining neighbors of the parent by
calling nextNeighbor(u, q + 1).
– findNextComponent: Check for another connected components by iterating through all adjacency arrays to find one that does not contain a single
pointer p with (A[p] = 0) ∨ (A[p] = n + 1). If there is one, go to the largest
position q ≤ p of the adjacency array in A to store the name of the corresponding vertex in some global variable s = Name[q] and to call visit(q).
Otherwise, we are done.
Since we destroyed only one of each pair of cross pointers, we can easily
restore them by iterating over all adjacency arrays. If we find a pointer (A[p] 6=
0)∧ (A[p] 6= n + 1) at a position p, then follow it and set A[A[p]] = p. So we have
restored the cross-pointer representation.
As in the previous subsection, ignoring the calls for the user-defined functions
and the function findNextComponent we make only tail-calls and require
consequently no recursion stack.
Theorem 7. There is an in-place DFS for undirected graphs in the restore
model that runs in O(n + m) time on n-vertex m-edge graphs with a representation consisting of n + 2m + 2 words and that calls all user defined functions.

5

Breadth-First Search

As usual for a BFS, our algorithm runs in rounds and, in round z − 1, all vertices
of distance z from a start vertex are added into a new list. Then our algorithm
can always iterate through a list of vertices and for each such vertex u, we iterate
through u’s adjacency array. For a simpler description, assume that all vertices
are initially white and whenever a vertex is added into the BFS tree, then it
turns light gray. If we are in the round where the vertex is processed, the vertex
is dark gray. After adding its white neighbors into the BFS tree, the vertex turns
black. The following description works on directed and undirected graphs.
To implement our BFS we make use of the following observation. In the
standard representation all words in T are stored in ascending order. Our idea is
to partition them in regions such that the most significant bits of the words are
equal per region. We use this to create a shifted representation of T by ignoring
the most significant bits and shifting the words in T together (Lemma 8) such
11

that we have a linear number of bits free to store a c-color choice dictionary [14,
Theorem 7.6] D as demonstrated in Fig. 9. We encapsulate the read access to
the words stored packed in T through a new data structure T . The details of
the access are described in the proof of Lemma 8.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

p1

p2

2

choice dictionary posit. & c′

packed words

Figure 9. Shifted representation with c-color choice dictionary.

Lemma 8. Let c > 0 be a constant. Having an array of n ≥ 2c+1 w ordered
words we can pack it in linear time with an in-place algorithm such that we
have cn unused bits free and that we still can access all elements of the array in
constant time. With a similar linear time in-place algorithm, we can unpack the
words.
Proof. The idea is to partition the words into parts such that each pair of words
in a part has the same c′ = c + 1 significant bits. Since the sequence is ordered,
′
we iterate over all words and look for the positions where one of the most 2c − 1
significant bits change. During the construction we remember all these positions
in the working memory.
Now, the most significant c′ bits of each word are equal per region. We treat
them as unused space and shift every of the packed words of w − c′ bit each
together. Stored packed, they occupy n(w − c′ ) bits in total such that it leaves
′
c′ n bits free to use. We use the last 2c words to store c′ and all the positions.
′
c′
′
Thus, c n − 2 w ≥ c n − n = cn bits remain free.
For implementing a function read(i) that reads the ith original word, we
have to identify its current position that can be distributed between two words, to
cut its bits out of the two words and to use the remembered position reconstruct
its most significant bits. For the following description assume that the bits of a
word are numbered from 0 (least significant) to w − 1 (most significant).
In detail, the ith word in T originally stored at position w(v − 1) was shifted
exactly c(v − 1) bits and now starts after x = (w − c)(v − 1) bits, i.e., it starts
with bit y = (x mod w) in the word ((x div w) − 1) and consists of the next w − c
bits. Using suitable shift operations we can get the ith word in constant time.
To reconstruct its most significant bits, scan the last c′ words to determine the
part to which i belongs.
To restore to the standard representation of the array, we store c′ and the positions in the working memory. Afterwards, we iterate over the words backwards
and set T [i] = read(i) for all i ∈ [1, n].

12

Before we now obtain our linear time BFS, we want to remark that the shifted
representation can not be used to run a standard DFS since a stack for the DFS
can require Θ(n log n) bits on n-vertex graphs.
We first prepare the shifted representation of our graph. Then we can use
the free bits to implement a c-color choice dictionary D in which we store the
colors of the vertices and to iterate over dark gray vertices in constant time per
vertex.
As described in [14], the c-color choice dictionary provides the following functions.
– iterate.init(c): Prepare an iteration over all entries with the color c.
– iterate.next(): Returns the next entry that is colored with the color c.
– iterate.more(): Returns true exactly when iterate.next can return an
entry colored as color c.
– setColor(c, v): Colors an entry v with the color c.
– color(v): Returns the color of the entry v.
To start our BFS at vertex v, we first initialize the c-color choice dictionary
D for four colors with all vertices being initially white. Remember in a global
variable a round counter z = 0 to output the round number for each vertex.
Then, color the root vertex v light gray by calling D.color(lightGray, v).
Finally, we start to process the whole DFS-tree as follows.
Whenever the current round counter z is even, we look for light gray vertices
and color their white neighbors dark gray and if z is odd we do vice versa. We
explain how to process the vertices if z is even. For an odd z, simple switch the
meaning of light gray and dark gray.
First, we call D.iterate.init(lightGray) to prepare the iteration over
the light gray vertices. Now we iterate over all light gray vertices using the
D.iterate.more function to check if there is another light gray vertex left to
process and D.iterate.next to get the next light gray vertex v. As long as we
have a light gray vertex v we output z as its round number, color all its white
neighbors dark gray, and color v black. For this, we iterate over v’s adjacency array starting at position p = T [v] and ending at q = T [v + 1] − 1 where T [n + 1] is
a pointer to the word strictly behind our graph representation. For every neighbor u = A[j] with p ≤ j ≤ q we check if D.color(u) = white and if so we
color u dark gray by calling D.setColor(darkGray, u), otherwise we ignore
it. After the iteration over v’s adjacency array we call D.setColor(black, v).
If the iteration over the light-gray vertices ends, we reiterate over all lightgray vertices again and color them black to finish the current round. If we could
color a vertex dark gray in the current round, then there are vertices left to
process. We increase z by one and start a new round by iterating now over the
dark gray colored vertices as described. If we could not color any vertices dark
gray, we have no vertices left to process and finish the BFS.
By Lemma 8, we can restore to the standard representation.
Theorem 9. There is an in-place BFS for directed graphs in the restore model
that runs in O(n + m) time on n-vertex m-edge graphs with a representation
consisting of n + m + 2 words.
13

5.1

BFS on Undirected Graphs

In the following, we present another linear-time in-place BFS that only works
on undirected graphs. For the following BFS, do not use a shifted representation.
Instead, we use the swapped begin-pointer representation where each word is a
pointer or a vertex name. In addition, we can use the redundancy of the edges
(each undirected edge is stored as a directed edge from its endpoints) to store
the depth of each vertex in the BFS-tree constructed.
Consider the situation that we are in round z and currently consider a vertex
u and we want to add a white neighbor v into the list for round z + 1. Then
the idea is to replace the entry u for the edge {v, u} in the adjacency array
of v by some extra information that helps us to build a list consisting of all
vertices of round z + 1. Moreover, we have to guarantee that we can use the
extra information to test quickly if a vertex is white or not. In detail, we use
the invariant that a vertex v is white if and only if v is not the start vertex and
the second entry in the adjacency array points to value that is not zero and at
most n. Note that we do not distinguish in our invariant if a vertex is gray or
black. A vertex is dark or light gray exactly if it is part of the list over which we
currently iterate or which we currently build, respectively. Therefore, we move
the extra information at the beginning of v’s adjacency array by swapping the
information of two edges in the adjacency array of v. In detail, assume that v’s
adjacency array starts in A at position p and the edge {u, v} in the adjacency
array of u is stored at position q. We then store the value of A[p + 1] in A[q] and
set A[p + 1] to the first position of the adjacency array of the last vertex that
was added to round z + 1 or to 0 if there is no such vertex. The swap is also
sketched in Fig. 10. Finally, output v as a vertex in depth z + 1, color it gray
and proceed with the next vertex in u’s adjacency array. If the iteration over all
vertices in round z is done, proceed with the vertices in the list for round z + 1.
Note that, after choosing one start vertex and coloring it gray, the invariant
is initially true. In the first round, the list consists of only that start vertex.

i

k

u

p

i

k

u

p

p p+1
...

v

j

p p+1
...

v

x

j

q
...

i

j

q
...

j

o
p

x x+1
...

o
p

w

x x+1
...

w

Figure 10: A white vertex v (above) is discovered from a vertex u and turns
gray (below). The previous discovered vertex is w. A[x + 1] points to the vertex
discovered before w.
14

Moreover, the pointer stored for the lists are values larger than n so that the
invariant holds again after coloring v gray. The only value we have to store is an
iterator over the current list and two pointers to the last vertex added into the
list for the current and the next round.
In detail our BFS runs as follows. Choose a start vertex v = Name(p) whose
adjacency array begins at index p. Then run bfs(p).
– bfs(p): (Initially starts the BFS on a vertex at the position p.) In a global
variable remember the start vertex v start = Name[p] and the current round
number z = 0. Output the vertex v start as a vertex of depth 0.
Increment the round number z by one and call addNeighborsOfVertex(p, 0) to create a list of adjacency arrays of vertices of depth 1. The call
returns a pointer p′ to the first such adjacency array of the list or 0 there is
none. If p′ is 0, we can discover no more vertices from v start and we finish.
Otherwise, we run the following two steps. First, we call runRound(p′ ) that
returns another pointer p′′ . Second, we increment z by one and set p′ = p′′ .
We repeat these two steps until p′′ = 0. Then the whole BFS tree is output.
– addNeighborsOfVertex(i, r): (Extends a list of adjacency arrays starting
at position r by the adjacency array of white neighbors of the vertex u =
Name(i) and returns a pointer the first adjacency array in the list or 0 if
there is none.) Iterate over the whole adjacency array of the vertex u using a
variable k until Name[k + 1] = u + 1 ∨ k > n + m + 1, but ignore the second
entry i + 1 for every u 6= v start since the adjacency array of the start vertex
is not linked and the second entry is still a pointer to a neighbor.
In each iteration step, whenever a pointer p = A[k] points at a white vertex
v = Name(p), we add it into the list for the next round. In detail, check if
isWhite(p) is true. If so, lookup the position of u (more exactly the position
of the begin pointer to u) in v’s adjacency array, i.e, the smallest position
q ′ ≥ p such that A[q ′ ] = i. Swap the words at position p + 1 and q ′ . Now the
edge pointing at u is stored at the second position and can be overwritten to
store a link to the currently first adjacency array in the list as follows. Write
the pointer r into the second word at index p + 1 and set the start pointer
r := p such that r is pointing at the start the list again.
After the iteration, return r.
– runRound(p): (Outputs every vertex of the list of adjacency array using p
as a pointer to the first adjacency array and returns a pointer to a list for the
next round or 0 if there is none.) Use a global variable r to store a pointer
at a linked list of adjacency arrays for the vertices of the next round and set
it initially to 0. In fact, we reuse the next-to-last such pointer.
We now iterate over all adjacency arrays in the list starting with p. In each
iteration check if we reached the end of the list by checking if p = 0. If so
return r. Otherwise, first output the vertex v = Name[p] as a vertex of depth
z. Then, link the white neighbors of v by calling addNeighborsOfVertex(p, r) that returns a pointer r′ pointing at the start of a new linked list.
Finally, set r = r′ and p = A[p + 1] to proceed with the next vertex of the
current round. Continue with the next round.
15

– isWhite(p): (Return true if the adjacency array starting at position p was
never visited.) An adjacency array was never visited if it does not belong to
the start vertex and is not linked. Therefore, return true exactly if both
Name(p) 6= v start and the second pointer points to a word x = A[A[p + 1]]
with 0 < x ≤ n.
Notice that excluding the functions isWhite and bfs, which both are not
recursive, all other function calls are tail-recursive. Consequently, we do not need
a recursion stack.
To restore the begin-pointer representation, we iterate over all adjacency
arrays and for each array, set the second entry to 0 and undo the swap by interchanging the second smallest pointer in the array with the second entry of the
adjacency array. Then we run the transformation to the standard representation,
but leave the zero entries unchanged. We so get a standard representation—
except one entry in each adjacency array is a zero. And finally, we run the
transformation to the cross-pointer representation to turn the zeros into the correct cross pointers. Two changes in the transformation: 1.) Step over a zero to
the next vertex name. 2.) When a vertex v points to a vertex w = A[T [v]], but
A[T [w]] < v. Let u be the vertex in A[T [w]]. Then the edge {u, w} was skipped
due to a zero. Search once in the adjacency array of u for the position p with
the 0. Set A[T [w]] = p as well as A[p] = T [w] and increment T [w] by one.
Theorem 10. There is an in-place BFS for undirected graphs in the restore
model that runs in O(n + m) time on n-vertex m-edge graphs with a representation consisting of n + 2m + 2 words.
We want to remark that we can also store the depth of each vertex inside
the representation. After iterating through the current list and building the
next list, we only have to iterate again through the current list and replace all
pointers of the list by the current round number. Nevertheless, we can restore
the representation as described above.

6

Acknowledgments

Andrej Sajenko acknowledge support of the Deutsche Forschungsgemeinschaft
(DFG), project SpaceeffGA (KA 4663/1-1).

References
1. Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer,
Günter Rote, and André Schulz. Reprint of: Memory-constrained algorithms for
simple polygons. Comput. Geom. Theory Appl., 47(3, Part B):469–479, 2014.
2. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono,
Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search
using O(n) bits. In Proc. 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 553–564. Springer, 2014.

16

3. Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira, and Kunihiko
Sadakane. Space-time trade-offs for stack-based algorithms. In Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013),
volume 20 of LIPIcs, pages 281–292. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2013.
4. Paul Beame. A general sequential time-space tradeoff for finding unique elements.
SIAM J. Comput., 20(2):270–277, 1991.
5. Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison,
and Godfried Toussaint. Space-efficient planar convex hull algorithms. Theor.
Comput. Sci., 321(1):25–40, 2004.
6. Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao
Satti. Frameworks for designing in-place graph algorithms. CoRR, abs/1711.09859,
2017.
7. Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, chain decomposition and st-numbering using O(n) bits. In Proc. 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64
of LIPIcs, pages 22:1–22:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,
2016.
8. Timothy M. Chan, J. Ian Munro, and Venkatesh Raman. Selection and sorting in
the “restore” model. In Proc. 25th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 2014), pages 995–1004. SIAM, 2014.
9. Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS
2016), volume 58 of LIPIcs, pages 28:1–28:12. Schloss Dagstuhl – Leibniz-Zentrum
für Informatik, 2016.
10. Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. Tight lower bounds
for st-connectivity on the NNJAG model. SIAM J. Comput., 28(6):2257–2284,
1999.
11. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient basic graph
algorithms. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of LIPIcs, pages 288–301. Schloss Dagstuhl
– Leibniz-Zentrum für Informatik, 2015.
12. Amr Elmasry and Frank Kammer. Space-efficient plane-sweep algorithms. In Proc.
27th International Symposium on Algorithms and Computation (ISAAC 2016),
volume 64 of LIPIcs, pages 30:1–30:13. Schloss Dagstuhl – Leibniz-Zentrum für
Informatik, 2016.
13. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci., 34(1):19–26, 1987.
14. Torben Hagerup and Frank Kammer. Succinct choice dictionaries. Computing
Research Repository (CoRR), arXiv:1604.06058 [cs.DS], 2016.
15. Torben Hagerup, Frank Kammer, and Moritz Laudahn. Space-efficient Euler partition and bipartite edge coloring. Theor. Comput. Sci., to appear, 2018.
16. Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected
Components and Recognition of Outerplanar Graphs. In Proc. 41st International
Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of LIPIcs, pages 56:1–56:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.
17. J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theor.
Comput. Sci., 12(3):315–323, 1980.

17

18. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proc.
39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998),
pages 264–268. IEEE Computer Society, 1998.

18

