Treasure Hunt with Advice

The node searching problem (a.k.a. treasure hunt) is a fundamental task performed by mobile agents in a network and can be viewed as an online version of the shortest path problem: an agent starts in a vertex of an unknown weighted undirected graph, and its goal is to reach a given vertex. The cost is the overall distance (measured by the weights of the traversed edges) traversed by the agent. We consider the setting in which the agent sees the identifier of the vertex it is located in, the weights of the incident edges, and also the identifiers of the neighboring vertices. We analyze the problem from the point of view of advice complexity: at the beginning, the agent has a tape with an advice string that gives some a priori information about the input instance. This information has no restricted form; instead, the aim is to study the relationship between the size of this advice and the competitive ratio that can be obtained. We give tight bounds of the form Θ(

n

/

r

) bits of advice for a competitive ratio

r

(possibly depending on the number of vertices

n

). In particular, this means that an a priori knowledge of any graph parameter (which would be of size

O

(log

n

)) cannot yield a competitive ratio better than Ω(

n

/log

n

). Moreover, we give a lower bound on the expected competitive ratio of any randomized online algorithm for treasure hunt.