Locating a target with an agent guided by unreliable local advice
Nicolas Hanusse, David Ilcinkas, Adrian Kosowski, Nicolas Nisse · 2010
We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2Ω(min d,k}), for any d,k = O(log n), even when G is a tree.