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.