Tree Exploration with an Oracle

We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of

particular

items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is

quantitative

: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency.

We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm

${\cal A}$

is measured by its

competitive ratio

, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value.

We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglog

D

, where

D

is the diameter of the tree. More precisely, for any constant

c

, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglog

D

–

c

, and we show that every algorithm using an oracle of size loglog

D

–

g

(

D

), for any function

g

unbounded from above, has competitive ratio at least 2.