Exploring sparse graphs with advice

Information and Computation, vol. 289, pp. 104950

Abstract

Graph exploration is a theoretical model of the crucial task of moving an agent through an unknown environment. Here, an algorithm has to guide an explorer through a network with n vertices and m edges, visiting every vertex at least once. We consider the fixed-graph scenario by Kalyanasundaram and Pruhs (ICALP, 1993), where the explorer sees all vertices reachable in one step, their unique names and their distance from the current position. The algorithm only learns the structure of the graph during computation. Therefore, we are interested in the amount of crucial a-priori information (the advice complexity) needed to solve the problem optimally. We look at graph exploration on directed graphs and focus on cyclic solutions. It is known that O(nlog⁡n) bits of advice are necessary and sufficient to compute an optimal solution for general graphs. We present algorithms with O(m) advice, thus improving the bound for sparse graphs.

Authors 2

1. Hans-Joachim Böckenhauer corresponding

   ETH Zurich

   Affiliation as printed

   Department of Computer Science, ETH Zürich, Zürich, Switzerland

2. Janosch Fuchs corresponding Aachen Computer Science

   RWTH Aachen University

   Affiliation as printed

   Computer Science, RWTH Aachen University, Aachen, Germany