A team of mobile agents, starting from distinct nodes of a network modeled as an undirected graph, have to meet at the same node and simultaneously declare that they all met. Agents execute the same algorithm, which they start when activated by an adversary or when an agent enter their initial node. While executing their algorithm, agents move from node to node by traversing edges of the network in synchronous rounds. Their perceptions and interactions are always strictly local: they have no visibility beyond their current node and can communicate only with agents occupying the same node. This task, known as gathering, is one of the most fundamental problems in distributed mobile systems. Over the past decades, numerous gathering algorithms have been designed, with a particular focus on minimizing their time complexity, i.e., the worst-case number of rounds between the start of the earliest agent and the completion of the task. To solve gathering deterministically, a common widespread assumption is that each agent initially has an integer ID, called label, only known to itself and that is distinct from those of all other agents. Labels play a crucial role in breaking possible symmetries, which, when left unresolved, may make gathering impossible. But must all labels be pairwise distinct to guarantee deterministic gathering?

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 \emph{distance-constrained exploration}. The \emph{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 $\mathcal{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 \emph{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.

A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure, or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch et al. [ 3 ] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s . The size of the tank is B = 2 (1+α) r , for some positive real constant α, where r , called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most ⌊ B ⌋ edge traversals between two consecutive visits at node s . Let e(d) be the number of edges whose at least one endpoint is at distance less than d from s . Awerbuch et al. [ 3 ] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d) . We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d ) and then show how to modify this algorithm to work in the model from Awerbuch et al. [ 3 ] with the same complexity. Thus, we refute the preceding 20-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ ( e(d) ) for all graphs, and thus our algorithms are also almost optimal.

Abstract Treasure hunt is finding a hidden inert target by a mobile agent. We consider deterministic algorithms for treasure hunt in trees. Our goal is to establish the impact of different kinds of initial knowledge given to the agent on the cost of treasure hunt, defined as the total number of edge traversals until the agent reaches the treasure. The agent can be initially given either a complete map of the tree rooted at its starting node, with all port numbers marked, or a blind map of the tree rooted at its starting node but without port numbers. It may also be given, or not, the distance from the root to the treasure. This yields four different knowledge types that are partially ordered by their precision. The penalty of a less precise knowledge type over a more precise knowledge type measures intuitively the worst‐case ratio of the cost of an algorithm supplied with knowledge of type over the cost of an algorithm supplied with knowledge of type . Our main results establish penalties for comparable knowledge types in this partial order. For knowledge types with known distance, the penalty for having a blind map over a complete map turns out to be very large. By contrast, for unknown distance, the penalty of having a blind map over having a complete map is small. When a map is provided (either complete or blind), the penalty of not knowing the distance over knowing it is medium.

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node $s$. The size of the tank is $B=2(1+α)r$, for some positive real constant $α$, where $r$, called the radius of the graph, is the maximum distance from $s$ to any other node. The tank of size $B$ allows the agent to make at most $\lfloor B\rfloor$ edge traversals between two consecutive visits at node $s$. Let $e(d)$ be the number of edges whose at least one extremity is at distance less than $d$ from $s$. Awerbuch, Betke, Rivest and Singh [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most $d$ at cost nearly linear in $e(d)$. We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost $\mathcal{O}(e(d) \log d)$, and then show how to modify this algorithm to work in the model from [3] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost $Θ(e(d))$ for all graphs and thus our algorithms are also almost optimal.

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance labeling scheme with labels of O(log^3 n) bits.

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting -- agents can, indeed, meet almost everywhere -- we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other.

We consider distributed representation scheme for trees, supporting some special relationships between nodes at small distance. For instance, we show that for a tree T and an integer k we can assign local information on nodes such that we can decide for two nodes u and v if the distance between u and v is at most k and if so, compute it only using the local information assigned. For trees withn nodes, the local information assigned by our scheme is binary label of log n + O(klog(klog(n/k))) bits, improving a recent result of Alstrup, Bille and Rauhe.