Two-Agent Tree Evacuation

Abstract

We study the problem of evacuating two agents from a tree graph, through an unknown exit located at one of the nodes. Initially, the agents are located at the same starting node; they explore the graph until one of them finds the exit through which they can evacuate. The task is to minimize the time it takes until both agents evacuate, for a worst case placement of the exit. We consider two communication models, global communication where the agents can communicate at any time, and local communication where the agents can only communicate if they are at the same node at the same time. We show that the problem is NP-hard in both cases. We then present a 4/3-approximation algorithm for global and a 3/2-approximation algorithm for local communication.