Rendezvous Problem

Definitions and mathematical statement

A network rendezvous problem involves two agents moving in a graph $G=(V,E)$ until they meet. An admissible strategy prescribes each agent's action from its permitted observations, internal state, and any allowed random choices, without messages from the other agent before rendezvous. The source asks for an optimal strategy and its background identifies expected meeting time as a possible objective, but does not specify the data needed to define that optimization.

For example, only after choosing a synchronous discrete-time vertex-meeting model could positions $X_t,Y_t\in V$, $t\in{\mathbb{Z}}_{\geq0}$, define \[ T=\inf\{t\geq0:X_t=Y_t\},\qquad \inf\varnothing=\infty. \] After also choosing an initial-position law $\mu$, a probability model for random choices, and an admissible strategy class $\mathcal A$, one possible quantitative target would be \[ \inf_{(\sigma_1,\sigma_2)\in\mathcal A}{\mathbb{E}}_{\mu,\sigma_1,\sigma_2}[T]. \] A demand for a strategy attaining this value is stronger than merely asking for its infimum. A worst-case criterion over initial positions would produce another problem. These are explicit schematic alternatives, not conventions fixed by the supplied wording.

In particular the source does not select a graph class or specify whether the graph is known, whether nodes or agents are labelled, how edges or ports can be distinguished, whether the agents have identical strategies, how much memory or sensing they have, whether randomization is permitted or shared, or whether movement is synchronous. It also does not say whether crossing in an edge counts as meeting, whether waiting is allowed, or how starts are chosen or staggered. Thus neither one feasible-strategy class nor one optimality criterion is determined.

The registry labels the entry open. The supplied literature triage dated 2026-08-17 labels the broad topic partially solved and reports algorithms for labelled agents in unknown graphs under explicit synchrony and sensing assumptions. It states that these model-dependent results do not yield a single optimal strategy for the incomplete source question.

Short English statement

Find optimal movement rules for two agents to meet in a network without communicating. A precise problem must first fix the graph, agent information and labels, movement and meeting rules, starting conditions, randomness, and the criterion used to compare strategies.

Sources

• Local UnsolvedMath registry, permanent ID 1367, source code catalogue entry, "Rendezvous Problem," including supplied literature triage dated 2026-08-17.
• D. Pelc et al., as listed in the supplied record, "Rendezvous of Distance-aware Mobile Agents in Unknown Graphs," arXiv:1406.2795: https://arxiv.org/abs/1406.2795. The supplied triage cites this as an example in which labels, graph knowledge, sensing and time assumptions are explicit; no complete author list is supplied.