Exploring sparse graphs with advice

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 ( n log ⁡ 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

• Hans-Joachim Böckenhauer
• Janosch Fuchs
• Walter Unger

Keywords

• Graph exploration
• Advice complexity
• Fixed-graph scenario