A general lower bound for collaborative tree exploration
Yann Disser∗,†

Frank Mousset‡,§
Andreas Noever‡,¶
Angelika Steger‡

Nemanja Škorić‡

arXiv:1610.01753v1 [cs.DM] 6 Oct 2016

October 7, 2016

Abstract
We consider collaborative graph exploration with a set of k agents. All agents start
at a common vertex of an initially unknown graph and need to collectively visit all
other vertices. We assume agents are deterministic, vertices are distinguishable, moves
are simultaneous, and we allow agents to communicate globally. For this setting,√we
give the first non-trivial lower bounds that bridge the gap between small (k ≤ n)
and large (k ≥ n) teams of agents. Remarkably, our bounds tightly connect to existing
results in both domains.
First, we significantly extend a lower bound of Ω(log k/ log log k) by Dynia et
al. on the competitive ratio of a collaborative tree exploration strategy to the range k ≤
n logc n for any c ∈ N. Second, we provide a tight lower bound on the number of agents
needed for any competitive exploration algorithm. In particular, we show that any
collaborative tree exploration algorithm with k = Dn1+o(1) agents has a competitive
ratio of ω(1), while Dereniowski et al. gave an algorithm with k = Dn1+ε agents and
competitive ratio O(1), for any ε > 0 and with D denoting the diameter of the graph.
Lastly, we show that, for any exploration algorithm using k = n agents, there exist
trees of arbitrarily large height D that require Ω(D2 ) rounds, and we provide a simple
algorithm that matches this bound for all trees.

1

Introduction

Graph exploration captures the problem of navigating an unknown terrain with a single
or multiple autonomous robots. In the abstract setting, we take the perspective of an
agent that is located at some vertex of an initially unknown graph, can locally distinguish
edges at its current location, and can choose an edge to traverse in its next move. Various
scenarios for graph exploration have been studied in the past, for diﬀerent graph classes and
diﬀerent capabilities of the agent(s). A fundamental goal of exploration is to systematically
visit all vertices/edges of the underlying graph. For settings where exploration is possible,
we typically ask for eﬃcient exploration algorithms, e.g., in terms of the number of edge
traversals.
In this paper, we consider collaborative exploration, where a set of k agents are initially located at some vertex of an unknown undirected graph. We assume agents to move
∗

Institute of Mathematics, TU Darmstadt, Germany. disser@mathematik.tu-darmstadt.de
Supported by DFG SPP 1736.
‡
Department of Computer Science, ETH Zurich, Switzerland.
{moussetf|anoever|nskoric|steger}@inf.ethz.ch.
§
Supported by grant no. 6910960 of the Fonds National de la Recherche, Luxembourg.
¶
Supported by grant no. 200021 143338 of the Swiss National Science Foundation.
†

1

deterministically, allow them to freely communicate at all times, and to have unlimited
computational power and memory at their disposal. In every round each agent may traverse any edge incident to its current location, where the edges incident to a vertex are
revealed when that vertex is visited for the ﬁrst time. The goal is to visit all vertices while
minimizing the number of rounds. More precisely, we are interested in the competitive ratio of an exploration strategy, i.e., the worst case ratio between the total number of rounds
it needs and the minimum total number of rounds needed to visit all vertices of the same
graph, assuming it is known beforehand. We prove new lower bounds for the best-possible
competitive ratio of any collaborative exploration algorithm. Our bounds hold even for
the much simpler setting of tree exploration. Note that since our results concern trees, it
makes no diﬀerence whether nodes can be distinguished, and whether the agents need to
visit all edges or not.
Let Tn,D denote set of all rooted trees with n vertices and height D. Each such tree
corresponds to an instance of the tree exploration problem in which all k agents start at
the root of the tree. Clearly, any oﬄine exploration algorithm needs Ω(n/k + D) rounds
to explore a tree in Tn,D using k agents. This is shown to be tight by the following oﬄine
exploration algorithm that explores the tree in Θ(n/k + D) rounds: start with the tree T ,
double its edges, ﬁnd an Eulerian tour C (of length 2n − 2), distribute the agents evenly
on C (this takes at most D rounds), and explore T by letting each agent walk along C for
O(n/k) rounds.
In the online setting, we can explore a tree in Tn,D with a single agent using a depthﬁrst traversal in time O(n) and thus we trivially have a competitive ratio of O(1) when
k is constant. On the other hand, with k ≥ ∆D agents, where ∆ is the maximum degree
of the tree, we can simply perform a breadth-ﬁrst traversal, which takes O(D) steps and
thus also has competitive ratio O(1). Observe that in the ﬁrst case n/k dominates the
lower bound on the oﬄine optimum, while in the second case D is dominating. We are
interested in the best-possible competitive ratios between these two extreme cases.
Surprisingly, Dereniowski et al. [12] showed that already a polynomial number k =
Dn1+ε of agents allows for a BFS-like algorithm that achieves a constant competitive
ratio. For smaller teams of agents, Fraigniaud et al. [18, 20] gave a collaborative algorithm
with competitive ratio O(k/ log k). This is only slightly better than the trivial upper
bound of O(k) that we get by performing a depth ﬁrst traversal with a single √agent. Ortolf
and Schindelhauer
[23] improved this competitive ratio to ko(1) for k = 2ω( log D log log D)
√
log D )
O(2
and n = 2
. The only non-trivial lower bound for collaborative tree exploration
was given by Dynia et al. [16]. They showed that any deterministic exploration algorithm
√
for k < n agents has competitive ratio Ω(log k/ log log k).

Our Results
We give the ﬁrst non-trivial lower bounds on the competitive ratio for collaborative tree
√
exploration in the domain k ≥ n (cf. Figure 1). More precisely, we show that for every
constant c ∈ N, any given deterministic exploration strategy with k ≤ n logc n agents has
competitive ratio Ω(log k/ log log k) on the set of all trees on n vertices. Note that this
√
extends the range of the bound by Dynia et al. [16] for k < n signiﬁcantly.
Secondly, we show that for every constant ε > 0, there is a constant D = D(ε) such
that for any exploration algorithm with k ≤ Dn1+ε agents, there exists a tree in Tn,D
on which the algorithm needs at least D/(5ε) rounds. This (almost) tightly matches the
algorithm of Dereniowski et al. [12], which can explore any tree in at most (1 + o(1))D/ε
rounds using k = Dn1+ε agents. Our result implies that any exploration algorithm with
k = D 1+o(1) agents has competitive ratio ω(1). More precisely, we get that for any function
2

comp. ratio

)
O(k

(1)

ko

20]
18,
[
k
g
k/ lo
O(1)
O(1)

Ω(log k/ log

Dε

√

[23]

O(1) [12]

log k) [16]

ω(1)
n logc n Dn1+ε

n

Ω(1)
∆D

k

Figure 1: State of the art in collaborative tree exploration. Upper bounds are green and
lower bounds are red. Thick lines show our results.
0 ≤ f (n) ≤ o(1), there is a function D = D(n) such that every exploration algorithm
with k = Dn1+f (n) agents has competitive ratio ω(1) on the trees in Tn,D . In contrast,
the algorithm of Dereniowski et al. shows that k = Dn1+ε agents are suﬃcient to get a
competitive ratio O(1) on such trees.
Finally, for every exploration algorithm with k = n, we construct a tree of height D =
ω(1) where the algorithm needs O(D 2 ) rounds. We give a simple algorithm that achieves
this bound in general.

Further Related Work
Many variants of graph exploration with a single agent have been studied in the past.
Any (strongly) connected graph with distinguishable vertices can easily be explored in
polynomial time by systematically building a map of the graph. Regarding the exploration
of undirected graphs with indistinguishable vertices, Aleliunas et al. [2] showed that a
random walk explores any graph in O(n3 ∆2 log n) steps, with high probability. In order
to turn this into a terminating exploration algorithm the agent needs Ω(log n) bits of
memory. Fraigniaud et al. [19] showed that every deterministic algorithm needs Ω(log n)
bits of memory, and Reingold [25] gave a matching upper bound. Disser et al. [14] showed
that alternatively Θ(log log n) pebbles and bits of memory are necessary and suﬃcient for
exploration, where a pebble is a device that can be dropped to make a vertex distinguishable
and that can be picked up and reused later. Diks et al. [13] showed that trees can be
explored with O(log ∆) memory, and that Ω(log n) memory is required if the agent needs
to eventually terminate at the start vertex. Ambühl [4] gave a matching upper bound for
the latter result.
For the case of directed graphs with distinguishable vertices, Albers and Henzinger [1]
gave an exploration algorithm with subexponential running time dO(log d) m that learns a
map of the graph. Here m denotes the number of edges and d is the deﬁciency of the
graph, i.e., the number of edges missing to make the graph Eulerian. This results narrows
the gap between a quadratic lower bound and an exponential upper bound introduced by
Deng and Papadimitriou [11].
3

An even more challenging setting (for the agent) is the exploration of directed, strongly
connected graphs with indistinguishable vertices. In general the agent needs exponential time to explore a graph in this setting. On the other hand, Bender and Slonim [7]
showed that two agents can explore any directed graph in polynomial time, using a randomized strategy. Bender et al. [6] showed that to accomplish this with a single agent we
need Θ(log log n) pebbles, i.e., “a friend is worth O(log log n) pebbles”. Remarkably, Bender
et al. [6] also showed that if the number of vertices is known beforehand, a deterministic
agent with a single pebble can explore any directed graph in polynomial time O(n8 ∆2 ).
The lower bounds for collaborative tree exploration discussed above carry over to the
collaborative exploration of general undirected graphs with distinguishable vertices. Also,
the algorithm of Dereniowski et al. [12] for k = Dn1+ε works on general graphs. Additionally, Ortolf and Schindelhauer [22] gave
best-possible competitive
√ a lower bound on the √
ratio for randomized algorithms of Ω( log k/ log log k) for k = n. Collaborative exploration by multiple random walks without communication has been considered by Alon et
al. [3], Elsässer and Sauerwald [17], and Ortolf and Schindelhauer [24].
Graph exploration has been studied in many other settings. Examples include tethered exploration or exploration with limited fuel [5, 15], exploration of mazes [8, 21], and
exploration of polygonal environments [9, 10].

2

Results

√
Our ﬁrst result extends the lower bound for k < n agents of Dynia et al. [16] to the much
larger range k ≤ n logO(1) n. We prove the following theorem:
Theorem 2.1. Let c be any positive integer constant. Then for every n and every 1 ≤
k ≤ n logc n there is some D = D(n, k, c) such that the following holds: for any given
deterministic exploration strategy with k agents, there exists a tree T on n vertices and
with height D on which the strategy needs
Ω


 log k
· (n/k + D)
log log k

rounds.
As mentioned above, there is an oﬄine algorithm that explores any graph with n
vertices and height D in time Θ(n/k + D). From this, we obtain the following corollary to
Theorem 2.1:
Corollary 2.2. Let c be any positive integer constant. Then any deterministic exploration
strategy using k ≤ n logc n has a competitive ratio of
Ω

 log k 
.
log log k

Our second main result shows that the algorithm of Dereniowski et al. [12] that explores
a graph with k = Dn1+ε agents in time (1 + o(1))D/ε is almost optimal: using k ≤ Dn1+ε
agents it is generally impossible to explore the graph in fewer than D/(5ε) rounds.
Theorem 2.3. Given any constant ε > 0 there is an integer D = D(ε) such that for
sufficiently large n and for every deterministic exploration strategy using k ≤ D · n1+ε
agents, there exists a tree on n vertices and with height D on which the strategy needs at
least D/(5ε) rounds.
4

In the range where k ≥ n, the oﬄine optimum is determined by the height D of the tree.
Therefore, the result of Dereniowski et al. mentioned above implies that the competitive
ratio is constant when k = D · n1+Ω(1) . Theorem 2.3 shows in particular that in some sense
this is tight:
Corollary 2.4. For any function 0 ≤ f (n) ≤ o(1), there is a function D = D(n) such
that the competitive ratio of any deterministic exploration strategy using k = D · n1+f (n)
agents is ω(1) on the the set Tn,D of all rooted trees with n vertices and height D.
Finally, it is possible for k = n agents to explore any tree on n vertices and of height
D in D 2 rounds using a breadth-ﬁrst exploration strategy. More precisely, we can split
the D 2 rounds in D phases of length D, and in each phase 1 ≤ i ≤ D do the following.
Let Ai be the set of unvisited leaves of the tree that is revealed at the start of phase i.
Then we send one agent to each vertex in Ai along a shortest path. This is clearly doable
in D rounds, and after D such phases, the tree is completely explored. We show that the
running time of D 2 is optimal up to a constant factor:
Theorem 2.5. For every n and every deterministic exploration strategy using k = n
agents, there exists a tree T on n vertices and with height D = ω(1) such that the strategy
needs at least D 2 /3 rounds to explore T .
In all the results above, we have considered the worst-case performance of an exploration
strategy on any tree. However, by looking at the proofs of Theorems 2.1 and 2.3, one can
see that the heights of our lower bound constructions are typically quite small. We believe
it is also natural to ask about the competitive ratio on the set of trees of height at least
D, for a given D. We show that at least for subpolynomial heights, the competitive ratio
with k = Θ(n) agents is unbounded:
Theorem 2.6. For any function D ≤ no(1) and any exploration strategy using k = Θ(n)
agents, the competitive ratio on the set of all trees of size n and height at least D is ω(1).
We stress that Theorem 2.6 diﬀers from the other results in that it applies to any height
D ≤ no(1) , while in the other results merely state that there exists some height with the
desired property.

3

Tree exploration games

In order to prove a lower bound on the competitive ratio, we consider a tree exploration
game deﬁned as follows. By a tree exploration game with k agents we mean a game with
two players, the explorer (the online algorithm) and the revealer (the adversary), played
according to the following rules. The game proceeds in rounds which we index by the
variable t (‘time’), the ﬁrst round being t = 0. The state of the game at time t is described
by a triple (Tt , At , φt ), where Tt is a rooted tree (the tree revealed at the beginning of
round t), At is a subset of the vertices of Tt (the subset of visited vertices by round t),
and φt : {1, . . . , k} → At is an assignment of the agents to the vertices (where φt (i) is the
location of the i-th agent at time t). In round t = 0 the revealer decides on the initial
tree T0 . The state at time 0 is then given by (T0 , A0 , φ0 ) where A0 = {root(T0 )} and
φ0 (x) = root(T0 ) for all 1 ≤ x ≤ k – that is to say, all agents are initially at the root of
T0 . In every round t > 0, each player can make a move. First, the explorer creates a new
assignment φt by moving each agent i to a neighbor of φt−1 (i) in Tt−1 or by keeping the
location of the agent same, i.e., φt (i) = φt−1 (i). Then the revealer decides on the new
5

tree Tt , where Tt must be obtained from Tt−1 by attaching (possibly empty) trees at some
vertices v ∈ V (Tt−1 ) \ At−1 , where V (Ti−1 ) is the set of vertices of Ti−1 . We then let
At = At−1 ∪ Nt where Nt = {φt (i) : 1 ≤ i ≤ k} is the set of the new agent locations. The
game ends in round t∗ if all vertices of Tt∗ are visited at the beginning of round t∗ , i.e., if
At∗ = V (Tt∗ ).
This type of game naturally lends itself to proving lower bounds for the time in which
k agents can explore an unknown tree. Speciﬁcally, consider any deterministic strategy
for exploring an unknown tree T with k agents. Such a strategy can be interpreted as
a strategy for the explorer in the tree exploration game with k agents. If the revealer
can play so that the game lasts for at least t∗ rounds, then this means that the proposed
exploration strategy needs t∗ rounds to explore the tree Tt∗ . We will use this observation
to prove lower bounds for the online graph exploration in the following section.
As a side remark, here it is crucial that the strategy is deterministic: if the strategy
were allowed to make random choices, then the tree Tt∗ would turn out to be a random
variable that might be highly correlated with the random choices made by the explorer,
and it could not serve as an instance on which the strategy performs badly.

4

Lower bound construction

We now give our lower bound construction that establishes the following technical lemma.
Lemma 4.1. Let n, L, m be positive integers such that n ≥ L · 16m . Then for any deterministic exploration strategy using
k≤

n1+1/m
6L(m + 1)2 (2L)1/m

agents, there
exists a tree T on n vertices and of height Lm such that the strategy needs at
m
least L 2 rounds to explore T .
Proof. Assume that integers n, L and m as above are given. Let k be any integer such that
1 ≤ k ≤ n1+1/m /(6L(m + 1)2 (2L)1/m ). To prove the lemma, we will describe a strategy
for the revealer in the tree exploration game with k agents such that

• the game does not end before round t∗ := L · m
2 , and
• the tree Tt∗ has height Lm and at most n vertices,

where the notation is as in Section 3. Note that this is enough to prove the lemma.
Before explaining the strategy, we ﬁx some notation. Let


i+1
1/m
α := (2L/n)
and ti := L ·
2
for 0 ≤ i < m. For each t ≥ 0 we can consider the equivalence relation ∼t on V (Tt ) where
u ∼t v if there exists a path between u and v in Tt that avoids the root of Tt (i.e., if they
have a common ancestor that is not the root). Since T0 ⊆ T1 ⊆ T2 ⊆ . . . are trees with the
same root, we will just write u ∼ v instead of u ∼t v without causing confusion. Then we
deﬁne at (v) := |{x | φt (x) ∼ v}|. In other words, at (v) counts the total number of agents
that could reach vertex v without passing through the root (under the assignment φt ). We
give the strategy for the revealer in Algorithm 1.

6

Algorithm 1: The strategy for the revealer.
begin
let T0 be a ‘star’ consisting of ⌈n/(2L)⌉ paths of length L from the root;
foreach round t = 1, 2, 3, . . . do
let the explorer choose φt ;
if t = ti for some 1 ≤ i < m then
let Ki be a maximal set of vertices in V (Tti −1 ) \ Ati −1 s.t.
(i) every vertex in Ki has distance L · i to the root in Tti −1
(ii) there are no two distinct vertices u, v ∈ Ki with u ∼ v.
let Si ⊆ Ki be the ⌈α|Ki |⌉ vertices v ∈ Ki with least ati (v);
deﬁne Tti by attaching at each v ∈ Si a path of length L − 1 with a star
with L · (i + 1) · ati (v) leaves at the end;
else
let Tt = Tt−1 ;
end
end
end

L
S1

S1

S1
L−1

S2
L−1

Figure 2: A sketch of the tree generated by the revealing strategy, for artiﬁcial values
α = 1/3 and ⌈n/(2L)⌉ = 9 (degrees in the actual construction are much larger). The actual
shape depends on the distribution of the agents at times t1 , t2 . Dashed lines represent paths
of the speciﬁed length.

For a better intuition, we refer the reader to Figure 4, which shows what the tree
constructed by this strategy might look like. We establish three claims which are used
to show that the algorithm indeed runs for at least t∗ = tm−1 rounds and that the tree
7

constructed in this way has the right properties.
Claim 1. For every 0 ≤ i < m the following holds. The height of Tti is at most L · (i + 1).
Moreover, if S1 , . . . , Si are all non-empty, then the height of Tti is exactly L · (i + 1).
Proof. The tree Tti diﬀers from Tti−1 if and only if Si is non-empty, and in this case it is
obtained by attaching trees of height L at some vertices with distance L · i to the root in
Tti−1 . Since Tt0 = T0 has height L, this implies the claim by induction.
Claim 2. For all 1 ≤ i < m and every v ∈ Si , there exists at least one descendant of v at
depth L · (i + 1) in Tti+1 −1 that does not belong to Ati+1 −1 . In particular, for all 1 ≤ i < m
we have |Ki+1 | = |Si |.
Proof. Each vertex at depth L(i + 1) is a descendant of some vertex v ∈ Si . Moreover, we
have u ≁ v for any two distinct u, v ∈ Si . Thus, the second claim follows directly from the
ﬁrst.
For the ﬁrst claim, consider any 1 ≤ i < m and v ∈ Si . Note that
(1) at time ti we create L · (i + 1) · ati (v) descendants of v at depth L · (i + 1);
(2) ti+1 − ti = L · (i + 1).
Because of this, no agent passing through the root can visit any descendant of v at depth
L · (i + 1) before round ti+1 . On the other hand, the ati (v) agents that could visit a
descendant at this depth without passing through the root cannot visit all descendants
before round ti+1 . Thus at least one descendant at depth L · (i + 1) must be unvisited at
the end of round ti+1 − 1.
Claim 3. For every 1 ≤ i < m we have the bounds
|Si | ≥

αi n
1
≥
2L
α

and

|Si | ≤

(2α)i n
.
2L

Proof. By deﬁnition we have α = (2L/n)1/m < 1 and thus αm = 2L/n, which gives us
αi n
αm−1 n
≥
= 1/α
2L
2L
for all 1 ≤ i < m.
For the lower bound, note that since A0 contains only the root, we have |K1 | =
⌈n/(2L)⌉. By the deﬁnition of Si , we have |Si | ≥ α|Ki | for all 1 ≤ i < m. Moreover,
if 2 ≤ i < m then by Claim 2 we have |Ki | = |Si−1 |. The lower bound then follows by
induction.
For the upper bound, note that K1 ≤ n/(2L) + 1 ≤ n/L, where the last inequality uses
n ≥ 2L. Moreover, using |Ki | ≥ 1/α we have |Si | ≤ α|Ki | + 1 ≤ 2α|Ki | for all 1 ≤ i < m.
Finally, if 2 ≤ i < m then |Ki | = |Si−1 | by Claim 2, and the upper bound follows by
induction.
Since |Si | > 0 implies in particular that Ati −1 6= V (Tti −1 ), we conclude from Claim 3
∗
that the game does not stop before reaching round tm−1 = L · m
2 = t . Moreover, from

8

Claim 1 and Claim 3 we see that Ttm−1 is a tree with height L · m. To complete the proof
we need to show that |V (Ttm−1 )| ≤ n. We have
|V (Ttm−1 )| ≤ ⌈n/(2L)⌉ · L + 1 +
m−1
X

≤ n/2 + L + 1 +

m−1
X

X

i=1 v∈Si

L(i + 1)

i=1

(L − 1 + L · (i + 1) · ati (v))
X

ati (v) +

m−1
X
i=1

v∈Si

|Si |(L − 1).

(1)

To bound the double sum note that
P |Ki | ≥ |Si | ≥ 1/α (Claim 3) implies that ⌈α|Ki |⌉ ≤
2α|Ki |. Note also that the sum v∈Ki ati (v) in (1) is at most k, as no two vertices u, v
from Ki are in the same subtree, i.e., u 6∼ v. Since Si contains the ⌈α|Ki |⌉ ≤ 2α|Ki |
vertices of Ki with least ati (v), we thus have
X
X
ati (v) ≤ 2α
ati (v) ≤ 2αk,
v∈Si

v∈Ki

and therefore
m−1
X

L(i + 1)

i=1

X

v∈Si

ati (v) ≤ L(m + 1)2 αk.

(2)

To bound the simple sum in (1), we use the upper bound from Claim 3 and obtain
m−1
X
i=1

|Si |(L − 1) ≤ (L − 1)

∞
X
(2α)i n
i=1

2L

=

∞

X
2αn
L−1
(2α)i ≤
· 2αn
.
2L
2 − 4α

(3)

i=0

Combining (1) with (2) and (3), we get
|V (Ttm−1 )| ≤ n/2 + L + 1 + L(m + 1)2 αk +

2αn
.
2 − 4α

(4)

Since n ≥ L · 16m ≥ 12L we have L + 1 ≤ 2L ≤ n/6. By the deﬁnition α = (2L/n)1/m and
the assumption k ≤ n1+1/m /(6L(m + 1)2 (2L)1/m ) we have
L(m + 1)2 αk = L(m + 1)2 (2L/n)1/m k ≤ n/6.
Finally, n ≥ L · 16m implies that α ≤ 1/8 and so the last term in (4) is also at most n/6.
Hence |V (Ttm−1 )| ≤ n/2 + 3n/6 = n.

5

Consequences for competitiveness

We now use Lemma 4.1 to derive consequences for best-possible competitive ratios of
collaborative tree exploration algorithms. In the proofs below, log is always to the natural
base e.
Theorem 2.1. Let c be any positive integer constant. Then for every n and every 1 ≤
k ≤ n logc n there is some D = D(n, k, c) such that the following holds: for any given
deterministic exploration strategy with k agents, there exists a tree T on n vertices and
with height D on which the strategy needs
 log k

Ω
· (n/k + D)
log log k
rounds.
9

√
Proof. By the result of Dynia et al. [16] it suﬃces to consider the case where k ≥ n. Let
n
c > 0 be a constant and assume k ≤ n logc n. We apply Lemma 4.1 with m = ⌈ (8+c)log
log log n ⌉
√
√
and L = ⌈n/(mk)⌉. Using k ≥ n, we have L = O( n) and m = o(log n) and thus
n ≥ L · 16m holds for suﬃciently large n. The lemma states that if
k≤

n1+1/m
6L(m + 1)2 (2L)1/m

(5)


then there is a tree of height D := Lm on which the strategy needs at least L m
2 =
Ω((n/k + D) · log k/ log log k) rounds. To complete the proof, we need to show that (5)
holds for all 1 ≤ k ≤ n logc n. We split the analysis to two cases. Let us ﬁrst assume
k ≥ n/m and thus L = 1. This implies
n1+1/m
n log8+c n
n1+1/m
≥ k,
≥
≥
24m2
6L(m + 1)2 (2L)1/m
24 log 2 n
when k ≤ n logc n and for suﬃciently large n.
Now we consider the case k < n/m. Using that assumption and the deﬁnition of L we
obtain L(m + 1)2 ≤ 4mn/k and 2L ≤ 4n/(mk). Putting it all together we have


 n 1/m
n
n1+1/m
k
mk 1/m
=
≥
≥ k,
6L(m + 1)2 2L
24m
4
6L(m + 1)2 (2L)1/m
√
where the last inequality holds for k ≥ n because, for suﬃciently large n,
(mk)1/m ≥ k1/m ≥ e

log n
2m

≥e

(8+c) log log n
4

≥ (log n)2 ≥ 100m.

Theorem 2.3. Given any constant ε > 0 there is an integer D = D(ε) such that for
sufficiently large n and for every deterministic exploration strategy using k ≤ D · n1+ε
agents, there exists a tree on n vertices and with height D on which the strategy needs at
least D/(5ε) rounds.
Proof. We choose L = 1 and m = ⌈1/2ε⌉ in Lemma 4.1. The claim is trivial unless
ε < 1/5, so we can eliminate rounding and assume generously that 1/m ≥ 1.4ε. The
condition n ≥ L · 16m is clearly satisﬁed for suﬃciently large n.

By Lemma 4.1, there is a tree T of height m that needs time m
2 ≥ m/(5ε) to be
explored, provided the team has size at most (for n suﬃciently large)
k ≤ n1+1.4ε /(12(m + 1)2 ) ≤ m · n1+ε = D · n1+ε .
Theorem 2.5. For every n and every deterministic exploration strategy using k = n
agents, there exists a tree T on n vertices and with height D = ω(1) such that the strategy
needs at least D 2 /3 rounds to explore T .
√
Proof. We choose L = 1 and m = ⌈ log n ⌉ in Lemma 4.1. Then n ≥ L · 16m holds for
suﬃciently large n. Note also that for suﬃciently large n,
√
n1+1/m
log n
/ log n) ≥ n.
=
Ω(n
·
e
12(m + 1)2

The lemma now states that there exists
a tree T of height m such that the given strategy
m
with k =
n
agents
needs
at
least
rounds
to explore T . Since for large enough n we
2

m
2
have 2 ≥ m /3, this implies the theorem.
10

Theorem 2.6. For any function D ≤ no(1) and any exploration strategy using k = Θ(n)
agents, the competitive ratio on the set of all trees of size n and height at least D is ω(1).
Proof. Suppose that D ≤ no(1) , i.e., D = n1/f (n) , where f (n) is a function which tends to
inﬁnity with n. Let L = D and note that we have
16L1/m
L1+1/m (m + 1)2
4m2 n2/f (n)
≤
≤
.
n1/m
n1/m
n1/m
If we choose m = m(n) = ω(1) as a function growing suﬃciently slowly such that we have
m ≤ min{(f (n))1/2 , (log n)1/2 }, then the following is true:
4m2 n2/f (n)
= 4 · e2 log m+2(log n)/f (n)−log n/m → 0.
n1/m
This implies 16L1/m = o(n1/m ) and L1+1/m (m + 1)2 = o(n1/m ). In particular, n ≥ L · 16m
for suﬃciently large n. Moreover, if n is large enough then k = Θ(n) implies
n1+1/m
n1+1/m
=
≥ k.
6L(m + 1)2 (2L)1/m
o(n1/m )
By Lemma
4.1, there exists a tree T with height Lm ≥ D on which the strategy needs

L m
=
ω(Lm)
rounds. Since k = Θ(n), the oﬄine optimum is O(Lm + n/k) = O(Lm),
2
so the competitive ratio on the set of trees of height at least D is ω(1), as claimed.

6

Conclusions

In this paper we presented new lower bounds for collaborative tree exploration. Including
our results, the following bounds are now known. For k = O(1) or k ≥ D · n1+ε agents,
a competitive ratio of Θ(1) can be achieved. For ω(1) ≤ k ≤ n logc n, the best-possible
competitive ratio is bounded by Ω(log k/ log log k), and no constant competitive ratio is
possible when n logc n ≤ k ≤ D · n1+o(1) . On the other hand, the best exploration algorithms for trees in the domain k ≤ D · n1+o(1) stay close to the trivial competitive ratio
of k (the best ratios are k/ log k and ko(1) , depending on the domain).
In summary, we now fully understand the domain where constant competitive ratios
are possible, but, outside this domain, a wide gap persists.

Acknowledgments
We would like to thank Rajko Nenadov for useful discussions.

11

Bibliography
[1] S. Albers and M. R. Henzinger. Exploring unknown environments. SIAM Journal on
Computing, 29(4):1164–1188, 2000.
[2] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoﬀ. Random walks,
universal traversal sequences, and the complexity of maze problems. In Proceedings
of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pages
218–223, 1979.
[3] N. Alon, C. Avin, M. Koucký, G. Kozma, Z. Lotker, and M. R. Tuttle. Many random
walks are faster than one. Combinatorics, Probability and Computing, 20(4):481–502,
2011.
[4] C. Ambühl, L. Gąsieniec, A. Pelc, T. Radzik, and X. Zhang. Tree exploration with
logarithmic memory. ACM Transactions on Algorithms, 7(2):1–21, 2011.
[5] B. Awerbuch, M. Betke, R. L. Rivest, and M. Singh. Piecemeal graph exploration by
a mobile robot. Information and Computation, 152(2):155–172, 1999.
[6] M. A. Bender, A. Fernández, D. Ron, A. Sahai, and S. Vadhan. The power of a pebble:
Exploring and mapping directed graphs. Information and Computation, 176(1):1–21,
2002.
[7] M. A. Bender and D. K. Slonim. The power of team exploration: Two robots can learn
unlabeled directed graphs. In Proceedings 35th Annual Symposium on Foundations of
Computer Science (FOCS), pages 75–85, 1994.
[8] M. Blum and D. Kozen. On the power of the compass (or, why mazes are easier to
search than graphs). In Proceedings of the 19th Annual Symposium on Foundations
of Computer Science (FOCS), pages 132–142, 1978.
[9] J. Chalopin, S. Das, Y. Disser, M. Mihalák, and P. Widmayer. Mapping simple
polygons: How robots beneﬁt from looking back. Algorithmica, 65(1):43–59, 2011.
[10] J. Chalopin, S. Das, Y. Disser, M. Mihalák, and P. Widmayer. Mapping simple
polygons. ACM Transactions on Algorithms, 11(4):1–16, 2015.
[11] X. Deng and C. H. Papadimitriou. Exploring an unknown graph. Journal of Graph
Theory, 32(3):265–297, 1999.
[12] D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk, and P. Uznański. Fast collaborative
graph exploration. Information and Computation, 243:37–49, 2015.
[13] K. Diks, P. Fraigniaud, E. Kranakis, and A. Pelc. Tree exploration with little memory.
Journal of Algorithms, 51(1):38–63, 2004.
[14] Y. Disser, J. Hackfeld, and M. Klimm. Undirected graph exploration with Θ(log log n)
pebbles. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 25–39, 2016.
[15] C. A. Duncan, S. G. Kobourov, and V. S. A. Kumar. Optimal constrained graph
exploration. ACM Transactions on Algorithms, pages 380–402, 2006.

12

[16] M. Dynia, J. Łopuszański, and C. Schindelhauer. Why robots need maps. In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 41–50, 2007.
[17] R. Elsässer and T. Sauerwald. Tight bounds for the cover time of multiple random
walks. Theoretical Computer Science, 412(24):2623–2641, 2011.
[18] P. Fraigniaud, L. Ga̧sieniec, D. R. Kowalski, and A. Pelc. Collective tree exploration.
Networks, 48(3):166–177, 2006.
[19] P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg. Graph exploration by a
ﬁnite automaton. Theoretical Computer Science, 345(2-3):331–344, 2005.
[20] Y. Higashikawa, N. Katoh, S. Langerman, and S.-i. Tanigawa. Online graph exploration algorithms for cycles and trees by multiple searchers. Journal of Combinatorial
Optimization, 28(2):480–495, 2012.
[21] F. Hoﬀmann. One pebble does not suﬃce to search plane labyrinths. In Proceedings
of the 3rd International Symposium on Fundamentals of Computation Theory (FCT),
pages 433–444, 1981.
[22] C. Ortolf and C. Schindelhauer. Online multi-robot exploration of grid graphs with
rectangular obstacles. In Proceedinbgs of the 24th ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA), pages 27–36, 2012.
[23] C. Ortolf and C. Schindelhauer. A recursive approach to multi-robot exploration of
trees. In Proceedings of the 21st International Colloquium on Structural Information
and Communication Complexity (SIROCCO), pages 343–354, 2014.
[24] C. Ortolf and C. Schindelhauer. Strategies for parallel unaware cleaners. Theoretical
Computer Science, 608:178–189, 2015.
[25] O. Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4):1–24,
2008.

13

