A lower bound of 4 for online graph exploration
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The authors study a problem where a single agent has to explore all parts of an unknown network and then return to the start. They show that any strategy the agent uses will, in the worst case, be at least 4 times less efficient than the best possible path if the network were known beforehand. They also find that simplifying assumptions about the agent's moves and the network's structure don't change this difficulty. This improves previous knowledge by raising the minimum known competitive ratio from about 3.33 to 4.
Authors
Julia Baligacs
Abstract
In the online graph exploration problem, a single agent needs to visit every vertex of an initially unknown graph, which is learned over time in an online fashion, and return to its starting position. We prove that the competitive ratio of this problem is at least 4, improving on the previously best known lower bound of 10/3. A key ingredient of our proof is showing that several restrictions can be imposed on the agent's behavior without affecting the competitive ratio. As a byproduct, we also obtain that certain graph properties, such as the triangle inequality or being subcubic, can be assumed without affecting the competitive ratio.