Edge exploration of anonymous graph by mobile agent with external help

Exploration of an unknown network by one or multiple mobile entities is a well studied problem which has various applications like treasure hunt, collecting data from some node in the network or samples from contaminated mines. In this paper, we study the problem of edge exploration of an n node graph by a mobile agent. The nodes of the graph are anonymous, and the edges at a node of degree d are arbitrarily assigned unique port numbers in the range 0, 1, . . . , d - 1. A mobile agent, starting from a node, has to visit all the edges of the graph and stop. The time of the exploration is the number of edges the agent traverses before it stops. The task of exploration can not be performed even for a class of cycles if no additional help is provided. We consider two different ways of providing additional help to the agent by an Oracle. In the first scenario, the nodes of the graph are provided some short labels by the Oracle. In the second scenario, some additional information, called advice, is provided to the agent in the form of a binary string. For the first scenario, we show that exploration can be done by providing constant size labels to the nodes of the graph. For the second scenario, we show that exploration can not be completed within time o(n(8/3)) regardless of the advice provided to the agent. We propose an upper bound result by designing an O(n(3)) algorithm with O(n log n) advice. We also show a lower bound Omega(n(8/3)) on the size of advice to perform exploration in O(n(3)) time. In addition, we have done experimental studies on randomly created anonymous graph to analyze time complexity of exploration with O(n log n) size advice.