Tradeoffs Between Cost and Information for Rendezvous and Treasure Hunt

In rendezvous, two agents traverse network edges in synchronous rounds and have to meet at some node. In treasure hunt, a single agent has to find a stationary target situated at an unknown node of the network. We study tradeoffs between the amount of information (mathitadvice) available mathita priori to the agents and the cost (number of edge traversals) of rendezvous and treasure hunt. Our goal is to find the smallest size of advice which enables the agents to solve these tasks at some cost C in a network with e edges. This size turns out to depend on the initial distance D and on the ratio fraceC, which is the mathitrelative cost gain due to advice. For arbitrary graphs, we give upper and lower bounds of O(Dlog(D· fraceC) +loglog e) and Omega(Dlog fraceC), respectively, on the optimal size of advice. For the class of trees, we give nearly tight upper and lower bounds of O(Dlog fraceC + loglog e) and Omega (Dlog fraceC), respectively.