Optimal graph exploration without good maps

A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class U, is called the overhead of algorithm A for the class U of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, or-in one case-close to smallest, overhead. While for the class of all graphs, depth-first search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at leastroot3 but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is 3/2. We also consider exploration of the class of lines (simple paths). In this case, depth-first search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is root3. Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is 7/5. An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms. (C) 2004 Elsevier B.V. All rights reserved