Tree Exploration with an Oracle

International audienceWe 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 {\em particular} items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is {\em 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 $\cA$ is measured by its {\em 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 $\log \log 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 $\log \log D -c$, and we show that every algorithm using an oracle of size $\log \log D -g(D)$, for any function $g$ unbounded from above, has competitive ratio at least 2