How to Meet at a Node of Any Connected Graph

Abstract

Two mobile agents have to meet at the same node of a connected graph with unlabeled nodes. This intensely researched task is known as rendezvous. The adversary assigns the agents different starting nodes in the graph and different integer labels from a set {1,… ,L}. Time is slotted in synchronous rounds. The adversary wakes up the agents in possibly different rounds. After wakeup, the agents move as follows. In each round, an agent can either stay idle or move to an adjacent node. Each agent knows its label but not the label of the other agent, and agents have no a priori information about the graph. They do not know L. They execute the same deterministic algorithm whose parameter is the agent’s label. The time of a rendezvous algorithm is the worst-case number of rounds since the wakeup of the earlier agent till the meeting. 
In most of the results concerning rendezvous in graphs, the graph is finite and rendezvous relies on the exploration of the entire graph. Thus the time of rendezvous depends on the size of the graph. This approach is inefficient for very large graphs, and cannot be used for infinite graphs. For such graphs it is natural to seek rendezvous algorithms whose time depends on the initial distance D between the agents. In this paper we adopt this approach and consider rendezvous in arbitrary connected graphs with nodes of finite degrees, and whose set of nodes is finite or countably infinite. Our main result is the first deterministic rendezvous algorithm working under this general scenario.
For any node v and any positive integer r, let P(v,r) be the number of paths of length r in the graph, starting at node v. For any instance of the rendezvous problem where agents start at nodes v₁ and v₂ at distance D, let P(v₁,v₂,D) = max(P(v₁,D),P(v₂,D)). It is well known that, for example in trees, Ω(D+P(v₁,v₂,D) +log L) is a lower bound on rendezvous time for such an instance. The time of our algorithm, working for arbitrary connected graphs of finite degrees, is polynomial in this lower bound.
As an application we solve the problem of approach for synchronous agents in terrains in the plane, in time polynomial in log L and in the initial distance between the agents in the terrain.