Tradeoffs between cost and information for rendezvous and treasure hunt

• In rendezvous, two agents traverse edges in rounds and have to meet at some node.
• In treasure hunt, an agent must find a fixed target at some node of the network.
• Objective: tradeoffs between the advice available to the agents and the cost.
• Results: bounds on the size of advice to achieve a given cost.

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 (advice) available a 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 CC in a network with ee edges. This size turns out to depend on the initial distance DD and on the ratio eC, which is the relative cost gain   due to advice. For arbitrary graphs, we give upper and lower bounds of O(Dlog(D⋅eC)+logloge) and Ω(DlogeC), respectively, on the optimal size of advice. For the class of trees, we give nearly tight upper and lower bounds of O(DlogeC+logloge) and Ω(DlogeC), respectively.