Graph exploration by a finite automaton

AbstractA finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d⩾3, there exists a planar graph of maximum degree d with at most K+1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω(Dlogd) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D+1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O(Dlogd) bits. We thus prove that the worst case space complexity of graph exploration is Θ(Dlogd) bits