2026-10-05T13:47:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23445 2025-10-02T10:55:20Z ddc:004 open_access

Graph Exploration: The Impact of a Distance Constraint Devismes, Stéphane Dieudonné, Yoann Labourel, Arnaud exploration graph mobile agent 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. [Christian A. Duncan et al., 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|. In [Petrisor Panaite and Andrzej Pelc, 1999], Panaite and Pelc 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 𝒪(|V|). Hence, a natural question is whether we can 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. in [Christian A. Duncan et al., 2006] and shows a fundamental separation with the task of exploration without constraint on the moves. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stéphane Devismes and Yoann Dieudonné and Arnaud Labourel 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.68 urn:nbn:de:0030-drops-234452 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.68 eng https://creativecommons.org/licenses/by/4.0/legalcode