2024/10/17 by Devismes, Stéphane, Dieudonné, Yoann, Labourel, Arnaud
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2410.13386
A mobile agent, starting from a node s of a simple undirected connected graph G=(V,E), has to explore all nodes and edges of G using the minimum number of edge traversals. To do so, the agent uses a deterministic algorithm that allows it to gain information on G as it traverses its edges. During its exploration, the agent must always respect the constraint of knowing a path of length at most D to go back to node s. The upper bound D is fixed as being equal to (1+α)r, where r is the eccentricity of node s (i.e., the maximum distance from s to any other node) and α is any positive real constant. This task has been introduced by Duncan et al. [ACM Trans. Algorithms 2006] and is known as distance-constrained exploration. The penalty of an exploration algorithm running in G is the number of edge traversals made by the agent in excess of |E|. Panaite and Pelc [J. Algorithms 1999] gave an algorithm for solving exploration without any constraint on the moves that is guaranteed to work in every graph G with a (small) penalty in O(|V|). Hence, a natural question is whether we could obtain a distance-constrained exploration algorithm with the same guarantee as well. In this paper, we provide a negative answer to this question. We also observe that an algorithm working in every graph G with a linear penalty in |V| cannot be obtained for the task of fuel-constrained exploration, another variant studied in the literature. This solves an open problem posed by Duncan et al. [ACM Trans. Algorithms 2006] and shows a fundamental separation with the task of exploration without constraint on the moves.