# Discrete Evacuation in Graphs with Multiple Exits

Piotr Borowiecki, Shantanu Das, Dariusz Dereniowski, Łukasz Kuszner

► To cite this version:

Piotr Borowiecki, Shantanu Das, Dariusz Dereniowski, Łukasz Kuszner. Discrete Evacuation in Graphs with Multiple Exits. Theoretical Computer Science, 2025, 1035, pp.115141. 10.1016/j.tcs.2025.115141. hal-04962371

HAL Id: hal-04962371

https://hal.science/hal-04962371v1

Submitted on 1 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Discrete Evacuation in Graphs with Multiple Exits*†

Piotr Borowiecki‡

Shantanu Das¶

Dariusz Dereniowski§

Łukasz Kuszner§||

## Abstract

In this paper, we consider the problem of efficient evacuation of mobile agents from distinct nodes in a graph to multiple exit nodes, while avoiding congestion and bottlenecks, and minimizing the total evacuation time. Each node in the graph can only hold one agent at a time, so the agents must choose their movements based on the locations of other agents to optimize the evacuation process. We consider two scenarios: the centralized (offline) and the distributed (online) setting. In the former one, the agents have complete information about the initial positions of other agents. In the distributed setting, agents lack prior knowledge of other agents' locations but can communicate locally with nearby agents and must adapt their strategy in an online fashion as they move and gather more information. In this study, we propose an offline polynomial time solution for determining the optimal evacuation strategy for all agents. In the online case, where agents can communicate at a distance of two in the graph, a constant-competitive algorithm is presented. Additionally, we demonstrate that when agents are heterogeneous and each type of agent can access only a certain subgraph of the original graph, computing the optimal strategy becomes NP-hard, even with full global knowledge. This result remains true even if there are only two types of agents or, even if the optimal evacuation time is a small constant.

**Keywords:** Discrete evacuation, Distributed algorithm, Mobile agents, Network flow, Collision-free

## 1 Introduction

Coordinated actions of multiple autonomous agents is a subject of study in many contexts. Frequently, the communication capabilities of agents are limited, and the exchange of information between agents is only possible when they are located close to each other, which creates challenges for coordination problems. We consider here the *evacuation* problem which requires multiple mobile entities to reach designated safe area, in a coordinated manner. This can correspond to evacuating a building with a crowd of people inside, who are required to quickly leave the building. One could also imagine other scenarios, e.g., a swarm of mobile robots that are required to gather in selected places (called *exits* in the context of evacuation terminology).

In practical situations it can be desired to calculate the evacuation strategy 'on the fly' — just at the time, when the evacuation process is about to start. In fact it is possible to compute a customized solution adapted to the current situation, depending on the number of

<footnote>‡Institute of Control and Computation Engineering, University of Zielona Góra, Poland.</footnote>

<footnote>§Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Poland.</footnote>

<footnote>¶Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France.</footnote>

<footnote>||Institute of Informatics, University of Gdańsk, Poland.</footnote>

<footnote>†Research partially supported by the Polish National Science Center grant DEC-2011/02/A/ST6/00201, by the Ministry of Science and Higher Education (Poland) subsidy for Gdańsk University of Technology, and by the ANR (France) project MACARON (anr-13-js02-0002).</footnote>

<footnote>*An extended abstract of a preliminary version of this work has been presented at SIROCCO 2016, the 23rd International Colloquium on Structural Information and Communication Complexity [3].</footnote>

<footnote>**Corresponding author: Dariusz Dereniowski (deren@eti.pg.edu.pl)</footnote>
agents and their locations. Centralized computation of the evacuation strategy has an important
drawback as the security of the system relies strongly on the central computing unit and the
communication between the central unit and agents. Hence, for the safety reasons, a distributed
approach could be a better solution. Indeed, some attention has been paid to the study of
non-centralized evacuation control systems for example assuming a usage of handheld devices
(like smartphones) by evacuees [13].

We consider a discretized version of the evacuation problem where agents move on edges of a
graph in discrete time steps, under the condition that no two agents may be on the same node at
the same time. There are multiple exits - which are specially marked nodes that allow any agent
arriving at such a node to be removed from the graph. The objective of an evacuation strategy
is to determine the moves of the agents that minimize the time after which all the agents have
been evacuated, i.e., removed from the graph.

In this paper we try to answer the question of how the lack of knowledge about the number
and initial positions of other agents can influence the quality of a solution, e.g., by creating
bottlenecks when too many agents try to approach the same exit. We compare distributed
(online) solutions to the problem, with centralized (offline) solutions. Another important issue
for evacuation is when the mobile agents have intrinsic characteristics preventing some of them
from visiting certain areas of the environment. For example, disabled people might not be able to
go through steep stairs inside a building. To address such situations, we consider a reachability
function defined for each of the agents separately and investigate the coordinated evacuation of
such heterogeneous agents.

1.1 Related Work

Evacuation models can be classified as macro- and microscopic [23], where macroscopic models
are based on dynamic network flows and do not take into account the characteristics of individual
evacuees while microscopic models rely on simulations in which the properties of each evacuee
are considered.

In this context, the evacuation problem has been widely described as an application of
flows over time (dynamic flows) in time expanded graphs [19, 20] (see, e.g., the PhD thesis by
Kappmeier [25] for a survey with lots of references). Graph based models are the first choice
in the street network modeling [24] but also such environments as buildings [2, 7] or caves [6]
can be modeled by graphs. In this case, additional properties of graphs can be considered
to reflect properties of the real network such as the transit times, connection capacities, node
capacities etc. The motivation for the graph model considered in this paper is lattice graph
based discretization in which the Euclidean space is divided into small polygon cells. Such an
approach has been mostly considered for the sake of microscopic simulations [25]. A special
case of evacuating two agents from a tree having a single exit has been studied in [15]. This
scenario being a special case of our more general setting, on one hand allows to aim for low
competitive ratios (4/3 for global and 3/2 for local communication) and on the other hand the
analysis is different. The most important difference lies in the fact that in our model the main
issue is to deal with *network congestions*.

Another type of investigations has been done in the context of distributed algorithms for
collaborative agents. The most studied cases in this context involve continuous environments
with a single exit. Chrobak et al. [8] investigate evacuation from the line (see also [4] for a
generalization to multiple rays). A substantial work has been done on evacuation through an
unknown exit from a disc shaped continuous space [5, 10, 12, 16, 22, 26]. The goal in these
papers is to minimize the time when the last agent reaches an exit, which is in contrast to a
collaborative search problem studied earlier [1], where the goal is to find an exit by the first
robot as fast as possible. Many of these results attempt to provide the best algorithms in terms
of the evacuation time, compared to the obvious optimal solution when the exit is known to the
agents. In the above investigations, the number of agents is small and the issue of congestion or
collisions does not appear at all. However, some of them have a comparable distributed model
to ours, but for continuous search space, i.e., communication upon meeting and (indirectly) the
knowledge of the search space [5].

It is worth observing that any exploration algorithm can be used to solve evacuation (see, e.g., [11]) but in most models this approach will not be efficient. This is also the case in our model since one can construct simple examples providing sublinear (or constant) evacuation time while each exploration algorithm takes $\Theta(n)$ steps.

## 1.2 Our Results

We now outline our model and results informally with appropriate references to the correspond-
ing theorems. We consider the evacuation problem in a discrete model, modeled as a simple
graph where the agents start from distinct nodes of the graph, and have to move to any of the
*exit* nodes using a sequence of edge traversals, avoiding collisions with other agents (see the
formal description of the problem in Section 2).

We start with the centralized variant of the problem in Section 3 where we assume that agents have full knowledge: (1) knowledge of the graph and the exits, and (2) knowledge of the initial location of all agents. In this scenario, we show that the time expansion technique gives a polynomial-time algorithm for general graphs.*

Section 4 is devoted to the distributed variant in which the assumption (2) above is dropped, i.e., the agents no longer know the position of other agents. However, the agents can communicate locally with nearby agents and their individual strategies have to be computed in an online fashion. We consider distributed evacuation strategies for trees (see Sections 4.1–4.5). In particular we prove that, there does not exist any $(2 - \Theta(1/k))$-competitive distributed algorithm for evacuation of $k$ agents from a tree (cf. Theorem 4.1). On the other hand, we give a constant-competitive distributed evacuation algorithm for trees (cf. Theorem 4.2).

In Section 5, we discuss the problem of evacuating heterogeneous agents, with an additional
constraint that each type of agent can only use a specific subset of edges in the graph (see the
similar approach applied to the rendezvous problem in [9, 14, 18]). This immediately leads to
computationally hard cases, even for simple instances of the problem. More precisely we show
that the problem is NP hard even for instances that allow strategies of length two i.e., all agents
should evacuate in two time steps (cf. Theorem 5.1). We also show that the problem remain
NP hard if there are only two types of agents, i.e., the edge set of the graph is partitioned
into two subsets $E_1$ and $E_2$, and each agent can move either along the edges in $E_1$ or $E_2$ (cf.
Theorem 5.2). We note that the former result is tight in the sense that an optimal single step
evacuation can be reduced to finding a matching in a bipartite graph.

# 2 Problem Statement

In this section we formulate the discrete evacuation problem. We are given a finite, simple, undirected graph $G = (V, E)$ with the node set $V$, edge set $E$ and two distinguished nonempty node subsets $H$, $X$ called *homebases* and *exits*, respectively. Each agent knows the graph and the location of all exit nodes. We also assume that the nodes of a graph have unique identifiers. Initially, the graph contains $k$ agents, each of which occupies one of the homebases in $H$ such that no two agents occupy the same node; also at this stage, each agent sets its identifier to a unique value ‘inherited’ from its homebase. Starting from its homebase each agent aims at

<footnote>*We note that full initial knowledge allows for a lack of agents’ communication as each of them can compute the moves of all agents. The agent achieves this simply by making in its local memory a simulation of the algorithms’ execution of other agents. Thus this gives the classical centralized approach.</footnote>
evacuating from the graph G through one of the exits in X. The exit to be used by an agent is not predetermined, i.e., its choice is up to each agent's individual strategy. Notice that $|H| = k$ and $H \cap X = \emptyset$.

The time taken by the evacuation process is divided into time steps of unit duration. The process is synchronous. In a single step each agent performs one of the following actions:

(A1) *moves*, i.e., changes its location from the currently occupied node to one of its neighbors,

(A2) an agent *stays still*, which means that it remains at the same node.

An agent that occupies an exit node *evacuates*, i.e., it is automatically removed from the graph. At the end of actions (A1) and (A2), in step $s$, the node occupied by agent $i$ is denoted by $v_i(s)$. Naturally, $v_i(0)$ stands for the initial position (the homebase) of the agent. A tuple $(v_1, \dots, v_k)$ of the above 'positioning' functions is called an *evacuation strategy* if for each agent $i \in \{1, \dots, k\}$ there is a step $s_i$ such that $v_i(s_i) \in X$ and for each pair of distinct agents $i, j$ in each step $s \in \{1, \dots, \min\{s_i, s_j\}\}$ it holds

$$v_i(s) \neq v_j(s). \qquad (1)$$

The length of an evacuation strategy $(v_1, \dots, v_k)$ is defined as $\max\{s_1, \dots, s_k\}$.

The decision version of the discrete evacuation problem EVAC we define as follows:

### DISCRETE EVACUATION (EVAC)

*Input:* A graph $G$, an integer $\ell$, a set $X$ of exits, a set $H$ of homebases occupied by $k$ agents.

*Question:* Does there exist an evacuation strategy $(v_1, \dots, v_k)$ of length at most $\ell$?

One of the basic assumptions, determining the nature of our solutions is condition (1) which equally applies to centralized as well as distributed evacuation strategies. As we will see, in our algorithms, we allow any pair of agents $i, j$ located in the neighboring nodes to perform action (A1) in a single step $s$ such that $v_i(s) = v_j(s-1)$ provided that $v_j(s-1) \neq v_j(s)$. This makes it possible to move many agents (e.g., a set of consecutive agents on a path) at the same time, rather than 'shifting' particular agents one-by-one in subsequent steps. Note that if two agents on adjacent nodes need to swap positions, this can be done *virtually* by simply exchanging the identifiers of the agents, instead of physically moving them, and thus avoiding collisions on an edge. In the distributed setting, we also use a *group swap* for a group of communicating agents, which is one of the key mechanisms for resolving the conflicts between the agents (see further details in Section 4.3).

## 3 Centralized Evacuation

In this section, using the classical results for the maximum flow problem (see e.g., [17]), we show that EVAC admits a polynomial-time algorithm. More precisely, for an input $(G, \ell, X, H)$ of EVAC we construct an *evacuation digraph* $Q = (U, A)$ for which there exists a flow of size $k$ if and only if the answer to EVAC is YES. For an illustration of the construction, see Figure 1.

**Construction 3.1.** First, let $V = \{v_1, \dots, v_n\}$ be the set of nodes of the given graph $G$ and let $Q_0, \dots, Q_\ell$ be $\ell + 1$ disjoint digraphs $Q_j = (V_j^{\text{in}} \cup V_j^{\text{out}}, A_j)$ with $V_j^{\text{in}} = \{v_{j,1}^{\text{in}}, \dots, v_{j,n}^{\text{in}}\}$, $V_j^{\text{out}} = \{v_{j,1}^{\text{out}}, \dots, v_{j,n}^{\text{out}}\}$ and the arc set $A_j = \{(v_{j,p}^{\text{in}}, v_{j,p}^{\text{out}}) \mid p \in \{1, \dots, n\}\}$. Now, the node set $U$ of the evacuation digraph $Q$ can be defined as consisting of all nodes of the above digraphs $Q_0, \dots, Q_\ell$ and the two additional nodes $s$ and $t$. More formally $U = \{s, t\} \cup V_0^{\text{in}} \cup V_0^{\text{out}} \cup \dots \cup V_\ell^{\text{in}} \cup V_\ell^{\text{out}}$. In
<figure><img src="image_2.png" /><figcaption>Figure 1: An example of evacuation digraph $\mathcal{Q}$ with distinguished sets $H$ and $X$ consisting of nodes corresponding to the homebases and exits in the represented graph $G$, and the two distinguished flow-paths $(s, v_{0,n}^{\text{in}}, v_{0,n}^{\text{out}}, v_{1,p}^{\text{in}}, v_{1,p}^{\text{out}}, t)$ and $(s, v_{0,q}^{\text{in}}, \dots, v_{\ell-1,q}^{\text{out}}, v_{\ell,1}^{\text{in}}, v_{\ell,1}^{\text{out}}, t)$ representing the evacuation strategies of two agents with their homebases in $v_n$ and $v_q$ in $G$, respectively (dashed lines represent arcs with the ends in $t$).</figcaption></figure>

order to obtain the arc set $A$ of $\mathcal{Q}$ we include all arcs in $A_0 \cup \dots \cup A_\ell$ and for each $j \in \{0, \dots, \ell-1\}$ we add arcs: $(v_{j,p}^{\text{out}}, v_{j+1,p}^{\text{in}})$ for each $p \in \{1, \dots, n\}$, and $(v_{j,p}^{\text{out}}, v_{j+1,q}^{\text{in}})$ if $\{v_p, v_q\} \in E(G)$. Finally, we add to $A$ the following arcs: $(s, v_{0,p}^{\text{in}})$ if the corresponding node $v_p$ of $G$ belongs to $H$, and $(v_{j,p}^{\text{out}}, t)$ whenever $v_p$ belongs to $X$ and $j \in \{0, \dots, \ell\}$. In other words, we add arcs from $s$ to all nodes in $V_0^{\text{in}}$ that correspond to the homebases, and the arcs to $t$ from all nodes in $V_0^{\text{out}} \cup \dots \cup V_\ell^{\text{out}}$ that correspond to the exits. All arcs in $\mathcal{Q}$ are assumed to have unit capacities. Clearly, given $(G, \ell, X, H)$ the corresponding evacuation digraph can be constructed in polynomial time. $\square$

**Lemma 3.1.** Let $\mathcal{Q}$ be an evacuation digraph constructed for the input $(G, \ell, X, H)$. There exists an $s-t$ flow of size $k$ in $\mathcal{Q}$ if and only if the answer to EVAC is YES for the input $(G, \ell, X, H)$.

*Proof.* Observe that every $s-t$ flow of size $k$ can be equivalently seen as a $k$-element family consisting of $st$-paths that share only the endnodes $s$ and $t$. The paths in such family we call the *flow-paths*.

Assume that we are given an $s-t$ flow of size $k$ in the evacuation digraph $\mathcal{Q}$, and that $P_i$ is one of the flow-paths. Note that the length of $P_i$, denoted by $d_i$, is odd, and that for the number $n_i$ of digraphs $Q_j$ having a common arc with $P_i$ it holds $n_i = (d_i - 1)/2$. Following Construction 3.1 observe that every flow-path can be represented as a list of nodes $(s, v_{0,p}^{\text{in}}, \dots, v_{n_i,q}^{\text{out}}, t)$, where $v_{0,p}^{\text{in}}$ and $v_{n_i,q}^{\text{out}}$ correspond, respectively, to the homebase $v_p$ and the exit $v_q$ in $G$. Also, for each $j \in \{0, \dots, n_i - 1\}$ the path contains the arc $(v_{j,p}^{\text{out}}, v_{j+1,q}^{\text{in}})$ and if $p \neq q$, then there is the corresponding edge $\{v_p, v_q\}$ in the graph $G$. In the context of possible agents' actions, this can be interpreted as action (A1), i.e., the move of the agent $i$ from $v_p$ to $v_q$. On the other hand, if $p = q$, then there is no corresponding edge in $G$ and the agent performs action (A2), i.e., it stays still in $v_p$. We note that in this part of the proof, the arcs $(s, v_{j,p}^{\text{in}})$, $(v_{j,p}^{\text{in}}, v_{j,p}^{\text{out}})$ and $(v_{n_i,q}^{\text{out}}, t)$ do not represent any particular action; for each agent $i$, however, the arc $(v_{n_i,q}^{\text{out}}, t)$ represents the evacuation of $i$. Finally, note that since flow-paths do not share any nodes except $s$ and $t$, condition (1) is satisfied. Thus, all arcs related to actions (A1) or (A2), ordered according to the direction of the flow-path, determine the sequence of actions taken by agent $i$, and since for each $i$ the number of such actions is bounded from above by $(d_i - 3)/2 = n_i - 1 \le \ell$, we conclude that there exists an evacuation strategy $(\nu_1, \dots, \nu_k)$ of length at most $\ell$.

Now, assume that we are given an evacuation strategy of length $\ell$ and that $\mathcal{Q}$ is the evacuation digraph constructed according to Construction 3.1. For each agent $i$, the relationships between
the actions (given by the strategy) and appropriate arcs of the digraph $\mathcal{Q}$ as well as their meaning, are the same as in the first part of the proof. So it is not hard to determine the path $P_i$ in $\mathcal{Q}$ that corresponds to the sequence of actions performed by the agent $i$ on its way from the homebase to the exit. It remains to argue that the paths determined for any two distinct agents are the flow-paths (i.e., they share only the nodes $s$ and $t$). Suppose, to the contrary, that this is not true. If so, then there must be a step $j$ and two arcs in $\mathcal{Q}$ that share either a node $v_{j,p}^{\text{out}}$ in $V_j^{\text{out}}$ or $v_{j,q}^{\text{in}}$ in $V_j^{\text{in}}$. In both cases, however, the corresponding edges and positioning of the agents in $\mathcal{G}$ clearly violate condition (1). This leads to a contradiction with the fact that $(\nu_1, \dots, \nu_k)$ is an evacuation strategy. Hence, the strategy determines the set of $k$ flow-paths, or equivalently an $s-t$-flow of size $k$. $\square$

Since the maximum flow problem is polynomial [17], we have the following.

**Theorem 3.1.** *There exists a polynomial-time algorithm for the problem EVAC.*

# 4 Distributed Evacuation

In this section we investigate a distributed evacuation in tree networks. We start with the description of our distributed evacuation model. Next, we give a general lower bound on the competitive ratio of any distributed algorithm on trees. In the following sections we formulate a distributed evacuation algorithm for trees and prove its constant-competitiveness.

## 4.1 Distributed Evacuation Model

In the distributed evacuation model each agent autonomously computes its strategy based on local information and communication with other agents it encounters. The model is synchronous, i.e., during each step, each agent communicates with the other agents (if possible), performs local computations to decide on its next action, then either it moves (A1) or stays still (A2) (recall that according to (1) each node can hold at most one agent at a time).

Our next assumption is that each agent $i$ knows in advance the graph $\mathcal{G}$, its own homebase $v_i(0)$ and the location of all exits $X$ in $\mathcal{G}$. As previously stated, all nodes of the network have unique identifiers, thus we assume that also all agents have such identifiers, since each agent may 'inherit' the identifier of its homebase. At this point, we mention that all of the above assumptions are crucial for obtaining a constant-competitive evacuation algorithm. If the structure of the network or the locations of the exits are unknown, then in worst case, a single agent has to explore the network, which is a different objective and significantly changes the dynamics of the problem (as explained in the last paragraph of Section 1.1).

In our evacuation model, no agent is initially aware of the number and locations of other agents. The agents, however, are able to communicate using the following communication model. Each agent can directly communicate with any other agent that is within a distance of at most 2 in the graph (by the *distance* of nodes $u$ and $v$, denoted by $\text{dist}(u, v)$, we mean the number of edges, i.e., the *length*, of a shortest $uv$-path). Note that the exchange of messages within distance of two (not just one) is an essential assumption that follows from the necessity of avoiding collisions between the agents. Otherwise two agents at distance two, being unaware of each other may decide to move to the same node. We assume that communication is instantaneous (or it takes negligible time compared to the duration of a time step). Thus, at the beginning of each step, any two agents can exchange any number of messages if the distance between them is not larger than 2. Agents can also use message passing to communicate indirectly with other agents via intermediate agents. In the following, a set of agents capable of communicating with each other is called a *group*. For example, see Figure 2 where the agents form two groups such that within each group any two agents can communicate either directly (if they are within the distance
of at most two, like, e.g., $i_j$ and $i_{j+1}$ for $j \in \{1, 2, 3\}$) or indirectly if $i_1$ and $i_j$ are at distance greater than two but there exist agents $i_2, \dots, i_{j-1}$ such that for each $p \in \{1, \dots, j-1\}$ the agents $i_p$ and $i_{p+1}$ are at distance at most 2. In this example, agents $i_1$ and $i_4$ can communicate by passing messages through agents $i_2$ and $i_3$. Since we do not impose any restrictions on the

<figure><img src="image_3.png" /><figcaption>Figure 2: Two groups of communicating agents (black nodes contain agents, while white are not occupied).</figcaption></figure>

amount of messages exchanged between any two agents at the beginning of each step, without loss of generality we assume that each agent begins each step by identifying the positions of all agents with whom it may communicate directly or indirectly (i.e. all agents in its group). This can be achieved by performing a broadcast algorithm by the agents and since this part is straightforward, we omit the details and assume also in our algorithms that each step begins with collecting information about all agents that can be reached directly or indirectly by an agent in that step.

## 4.2 The Lower Bound

The measure we use in the analysis of the performance of evacuation algorithms is the competitive ratio, i.e., the worst case ratio of the evacuation time achieved by the distributed algorithm to the optimum offline evacuation time $t_{\text{opt}}$. We consider the worst case scenario over all tree networks and all possible locations of homebases and exits.

**Theorem 4.1.** There does not exist any $(2-\Theta(1/k))$-competitive online algorithm for distributed evacuation in a tree with $k > 1$ agents and multiple exits.

*Proof.* Given two integers $k > 1, p \ge 1$, let us consider a tree with $3kp + 1$ nodes: a node $v_0$ and $3kp$ nodes $v_{i,j}$, where $i \in \{1, \dots, k\}$ and $j \in \{1, \dots, 3p\}$. There are $k+1$ exits, i.e., $X = \{v_0, v_{1,3p}, v_{2,3p}, \dots, v_{k,3p}\}$. Node $v_0$ is adjacent to $k$ nodes: $v_{1,1}, v_{2,1}, \dots, v_{k,1}$ and for every $i \in \{1, \dots, k\}$ and $j \in \{1, \dots, 3p-1\}$ there is an edge $\{v_{i,j}, v_{i,j+1}\}$. There are $k$ agents $a_1, \dots, a_k$, where $\nu_{a_i}(0) = v_{i,p}$. Informally speaking, there are $k$ paths of length $3p$ joined by an exit node $v_0$, with $k$ agents, one in each path, placed $p$ steps away from the exit $v_0$ and $2p$ steps from the other exit $v_{i,3p}$ at the end of the path (see Figure 3 for an illustration).

In what follows we assume that $k = 4p$ (note that the optimal evacuation time for such instances is $t_{\text{opt}} = 2p$). Let $A$ be any distributed algorithm for evacuation. Consider the step $2p-2$ of the execution of $A$. We need to distinguish the following two cases:

(i) There exists $i \in \{1, \dots, k\}$ such that there is an agent $a$ on the path connecting $v_{i,p+1}$ and $v_{i,3p-2}$. Clearly $a = a_i$. Note that the agent $a_i$ was unable to reach the node $v_{i,1}$ adjacent to the exit $v_0$ and thus this agent performed no communication with another agent within the first $2p-2$ steps. Let us now consider a different instance of the problem in which the graph is the same as in the former one but there exists only one agent, namely $a_i$ with the same homebase
<figure><img src="image_4.png" /><figcaption>Figure 3: A tree of order $3kp + 1$ used in the proof of Theorem 4.1</figcaption></figure>

$v_{i,p}$. Thus, the input to the algorithm executed by the agent $a_i$ is the same as in the previous scenario. Therefore, due to the lack of communication as argued above, the behavior of the agent $a_i$ is exactly the same in the latter scenario as in the former one. Thus, the agent $a_i$ will not evacuate before step $2p$. Note that the optimal evacuation time for this instance with a single nonevacuated agent is $p$ and hence, in this case, the competitive ratio is 2.

(ii) In the second case, every agent $a_i$ is somewhere on the path $v_{i,1}, v_{i,p}$ or already evacuated during the first $2p-2$ steps. If $a_i$ evacuated, then clearly the exit it used is $v_0$. We consider two additional subcases. In the first subcase, all agents evacuate through $v_0$. Since $k = 4p$ and $t_{\text{opt}} = 2p$, the competitive ratio is at least 2 as required. In the second subcase, some agent $a_i$ evacuates through the exit $v_{i,3p}$. But then, $a_i$ needs to traverse the path connecting $\nu_{a_i}(2p-2)$ and $v_{i,3p}$ in steps that follow the step $2p-2$. This path contains the path of length $2p$ connecting $v_{i,p}$ with $v_{i,3p}$. Thus, $a_i$ does not evacuate within the first $(2p-2)+2p$ steps. Therefore, in the second subcase, the competitive ratio we obtain is greater than $\frac{4p-2}{2p}$. This gives the claimed lower bound, since $p = \Theta(k)$. $\square$

## 4.3 Evacuation in Tree Networks – Preliminaries

Before describing our evacuation algorithm, we need some additional definitions.

The exit associated with node $v$ is the exit $x \in X$ with the smallest identifier among the exits at the minimum distance from $v$. By the primary exit of agent $i$, denoted by $\text{pe}(i)$, we mean the exit associated with the homebase $\nu_i(0)$ of the agent. Clearly, there may be many agents having the same primary exit but for each agent the primary exit is unique. Also note that since primary exit of an agent depends only on the location of agent's homebase, it remains the same even when agent changes its position during the evacuation.

As we will see in the next section, in the early stage of evacuation each agent attempts to evacuate through its primary exit. This leads to the grouping of agents at exits, which allows them to communicate and compute a common strategy, rather than individual strategies. In the computed group strategy, each agent $i$ is assigned its secondary exit $\text{se}(i)$, i.e., the exit to be reached in the second stage of evacuation (those agents with secondary exits different from the primary one are treated as diverted in order to relieve the primary exit).

Based on the concept of primary exits, we define the partition $(V_{x_1}, \dots, V_{x_\eta})$ of the node set $V$ of a given tree $T$ with the set of exits $X = \{x_1, \dots, x_\eta\}$. Namely, for each exit $x \in X$, the set $V_x$ of the partition consists of all nodes $v$ such that $x$ is associated with $v$. From the viewpoint of an agent $i$ with the homebase in $V_x$, the node $x$ is its primary exit $\text{pe}(i)$. Naturally, $\cup_{x \in X} V_x = V(T)$ and since primary exits are uniquely determined, for every pair of distinct exits $x_p, x_q$ we have $V_{x_p} \cap V_{x_q} = \emptyset$. Moreover, for each $x \in X$ the subgraph induced by $V_x$ is connected. In what follows we use $T_x$ to denote the subtree induced by $V_x$.

At the beginning of computation, each agent roots $T$ at the node with the smallest identifier. This ensures that all agents select the same root, say $v_r$, belonging to the tree $T_x$ that contains
the exit $x_r$ (see in Figure 4(a), where $r = 2$). This allows the construction of unique tree $\tilde{T}$ with the node set $X$, the root $x_r$, and an edge between each pair of nodes $x_p, x_q$ for which $T$ contains an edge $\{v, u\}$ such that $v \in V_{x_p}$ and $u \in V_{x_q}$, where $p, q \in \{1, \dots, \eta\}$. For an example see Figure 4(b), where $x_1, x_4$ correspond to the vertices $v, u$ in Figure 4(a). Alternatively, note that $\tilde{T}$ can be obtained by contracting all edges of $T_x$ for each $x \in X$. Now, following 'away from the root' natural orientation of the edges of $\tilde{T}$ each agent can easily relate the subtrees $T_x$ of $T$. Namely, for any two exits $x_p, x_q$ we say that $T_{x_p}$ is a child of $T_{x_q}$ if $x_q$ is the parent of $x_p$ under the above orientation of $\tilde{T}$. The notion of descendant we use in a usual way, while by an *indirect descendant tree* we mean a descendant tree that is not a child tree.

<figure><img src="image_5.png" /><figcaption>Figure 4: Tree $T$ with exits $x_1, \dots, x_6$, subtrees $T_{x_1}, \dots, T_{x_6}$, and the corresponding tree $\tilde{T}$.</figcaption></figure>

As we have already mentioned, the moves of agents in the early stage of our algorithm result in gathering the agents at their primary exits. To address this process more accurately we define a special type of group. Namely, by a *group of agents at exit *x* in step *s**, denoted by $G_x(s)$, we mean the set of those agents $i$ for which $\nu_i(s) \in V(T_x)$ and each node of the path connecting $\nu_i(s)$ and $x$ is occupied by some agent belonging to $G_x(s)$. Note that the subgraph induced by the nodes occupied by $G_x(s)$ is connected and hence the agents in $G_x(s)$ can communicate with each other. Since $x$ is often a cut node, there may be more than one group at the same exit $x$ (see, e.g., the exit $x_2$ in Figure 4, where there may be even three groups at $x_2$). We say that agent $i$ joins the group $G_x(s)$ in step $s$ if $i \notin G_x(s-1)$ but $i \in G_x(s)$ (we allow the group to be empty before step $s$). The set of all agents we denote by $\mathcal{A}$, while $A_x$ stands for the set of all agents with their homebases in $V_x$ that is $A_x = \{i \in \mathcal{A} \mid \text{pe}(i) = x\}$. Clearly $\bigcup_{x \in \mathcal{X}} A_x = \mathcal{A}$.

As we will see later, the relationships resulting from the structure of $\tilde{T}$ are crucial in our algorithm. In particular, in our algorithm we will assume that the secondary exits in group strategies will be located neither in indirect descendant nor parent trees. In the second stage of the algorithm, this will 'direct' the flow of agents and significantly simplify the analysis of algorithm's effectiveness. This will also enable the description and resolution of conflicts between the agents. In this context, the parent-child relationship will be used, e.g., to set the priority for distinguished groups of agents, which will allow them to reach their secondary exits in appropriate time. For this purpose, we need the already mentioned *group swap* and a simple notion of *giving a way*. For clarity, we describe them here, before the formulation and analysis of the algorithm.

Namely, the *group swap* operation, consists in exchanging agent's identities within the group so that the agents in the distinguished subgroup get closer to their destination node.

Let us illustrate the idea of this operation with an example. Suppose we have a path with $p+q$ consecutive nodes $v_1, \dots, v_{p+q}$, where $v_1, \dots, v_p$ are occupied by the distinguished agents
$a_1, \dots, a_p$ moving towards $v_{p+q}$, while $v_{p+1}, \dots, v_{p+q}$ are occupied by the agents $b_1, \dots, b_q$ moving towards $v_1$. The group swap consists in exchanging identities between the agents such that after the operation the nodes $v_1, \dots, v_q$ are occupied by the agents $b_1, \dots, b_q$, while $v_{q+1}, \dots, v_{q+p}$ hold agents $a_1, \dots, a_p$, respectively. Specifically, in this example, each agent gets closer to its destination. Clearly, in general the groups do not have to be 'linear', as in our example, but also in that case it is not hard to see that agents can compute a sequence of identity swaps resulting in every agent of the distinguished group moved closer to its destination node (since in the evacuation strategies we consider only the number of steps as the optimization criterion, we neglect the computation time of this operation and conclude that such a group swap is computable).

The priority of movement has to be ensured when the routes of the two groups have only one node in common (the *crossroad node*). In such situation, a simple rule of *giving a way* can be used, which means that all agents of the lower priority group stay still until the last agent of the higher priority group leaves the crossroad node.

In the next section we describe our algorithm, where *giving a way* and *group swap* mechanisms can potentially be used in the second loop of Procedure 1 as well as the reverse phase in line 9 of Procedure 2.

## 4.4 Evacuation in Tree Networks – Algorithm Formulation

In order to describe the algorithm, we introduce the two procedures. First, we give our main evacuation procedure that achieves a constant competitive ratio, provided it is given an upper bound $B$ on the optimal evacuation time $t_{\text{opt}}$. Then, we describe the second procedure that uses 'doubling technique' consisting in subsequent calls to the first procedure with exponentially increasing value of the input parameter $B$. This allows to disregard the assumption that an upper bound on the evacuation time is known in advance. The competitive ratio of this procedure increases by a constant multiplicative factor with respect to the competitiveness of the first one.

**Procedure 1: BoundedDTE $(T, B)$ for an agent $i$**

**Input:** the underlying tree $T$, the time bound $B$.

1. **for** $k = 1$ **to** $B$ **do**

2. &nbsp;&nbsp;&nbsp;&nbsp;If possible, then move to the adjacent node that is closer to $pe(i)$.

3. **end for**

4. Compute the optimal evacuation strategy for the group $G_{pe(i)}(B)$ taking into account $pe(i)$ and exits in the child subtrees of $T_{pe(i)}$. Set secondary exit $se(i)$ according to the computed strategy.

5. **for** $k = 1$ **to** $8B$ **do**

6. &nbsp;&nbsp;&nbsp;&nbsp;If possible, then move to a node that is closer to $se(i)$.

7. **end for**

Let us start with the description of the first procedure, called **BoundedDTE** (*Bounded Distributed Tree Evacuation*; see Procedure 1). The procedure can be seen as having two phases, where the general idea of the first phase is as follows: since initially the homebases can be 'spread' so that the communication between the agents is not possible, each agent simply moves in the direction of its primary exit. This leads to gradual formation of 'more compact' configurations of agents (the groups at the exits). In fact the process depends on the input parameter $B$, in the sense that for each exit $x$, only the agents in $T_x$ that occupy the nodes at distance at most $B$ from $x$ are allowed to move towards $x$ to form a group at $x$. All other agents in $T_x$ just stay still, which will be ensured by omitting the execution of Procedure **BoundedDTE** for
those agents who should stay still. The phase of group formation is guaranteed to complete in $B$ steps (see Lemma 4.2). As soon as groups are formed at the exits, they calculate their own evacuation strategies, which they will realize in the second phase. According to the computed group strategy, some agents in the group at the exit $x$ will remain to evacuate through $x$, while others may be directed to the exits in selected child trees of $T_x$ (we justify the effectiveness of this choice in the proof of Lemma 4.3).

The strategy of each group is calculated locally, in the sense that it ignores any agents which do not belong to the group. Since the group formation process takes some amount of time, it is worth noting that at the moment when the group's strategy becomes known, some agents may have already evacuated through their primary exits.

**Procedure 2: DTE ($T$) for an agent $i$**

**Input:** the underlying tree $T$.

1: $B \leftarrow 1$

2: **while** true **do**

3: $B \leftarrow 2B$

4: **if** $\text{dist}(\nu_i(0), \text{pe}(i)) > B$ **then**

5: stay immobilized for the next $18B$ steps.

6: **else**

7: Call Procedure **BoundedDTE**($T$, $B$) for the agent $i$.

8: **if** $i$ is not evacuated **then**

9: Reverse $9B$ steps performed by **BoundedDTE** thus reaching the homebase.

10: **end if**

11: **end if**

12: **end while**

Concerning the idea of the second procedure, called DTE (Distributed Tree Evacuation; see Procedure 2), recall that the procedure systematically doubles the value of $B$, thus ‘trying to guess’ an upper bound on $t_{\text{opt}}$, and simply calls Procedure **BoundedDTE** with the current value of $B$ as its input. As we prove later (see Lemma 4.1) if $B$ is indeed at least $t_{\text{opt}}$, then every agent who executes Procedure **BoundedDTE** successfully evacuates. Otherwise, the agent who has not yet evacuated, reverses its moves walking back to its homebase, then **BoundedDTE** with a new guess $B$ is called.

## 4.5 Evacuation in Tree Networks – Algorithm Analysis

**Lemma 4.1.** If $B$ is an upper bound on $t_{\text{opt}}$, then Procedure **BoundedDTE** evacuates the executing agent in $9B$ steps.

In order to prove Lemma 4.1 we use Lemmas 4.2 and 4.3 stated below.

**Lemma 4.2.** If $\text{dist}(\nu_i(0), \text{pe}(i)) \le B$, then the first loop in Procedure **BoundedDTE** (lines: 1–3) finishes in $B$ steps resulting in the executing agent either evacuated or joined the group at its primary exit.

*Proof.* Let $i$ be the executing agent, and let $P(s) \subseteq T$, for $s \in \{0, 1, \dots, B\}$, be the maximal subpath of the path between $\nu_i(s)$ and $\text{pe}(i)$ such that $\nu_i(s) \in V(P(s))$ and for every node $v \in V(P(s))$ there exists an agent $j$ such that $\nu_j(s) = v$. Denote by $b(P(s))$ the endnode of $P(s)$ different than $\nu_i(s)$. Thus, the path $P(s)$ connects $b(P(s))$ with $\nu_i(s)$ and is fully occupied by agents. In an extreme case it may be that $b(P(s)) = \nu_i(s)$. In the context of this definition, to prove the lemma we need to argue that $\text{dist}(b(P(s)), \text{pe}(i)) = 0$ in some step $s$.
We first prove that for each step $s \ge 0$ it holds

$$ \mathrm{dist}(\mathrm{pe}(i), b(P(s))) > \mathrm{dist}(\mathrm{pe}(i), b(P(s+1))). \quad (2) $$

Denote by $u$ the neighbor of $\nu_i(s)$ that is closer to $pe(i)$ than $\nu_i(s)$ and by $b'$ the neighbor of $b(P(s))$ that is closer to $pe(i)$ than $b(P(s))$. Note that we may assume that such a $b'$ exists for otherwise the lemma is proved. Two cases may occur. In the first one the agent $i$ moves in this step. This implies that it gets from $\nu_i(s)$ to $u$ which gives that for each node $x$ of $P(s)$ the agent at $x$ also moves towards $pe(i)$. This proves (2). In the second case the agent $i$ does not move. Denote by $u_1 = u, u_2, \dots, u_q = b(P(s))$ the subsequent vertices of $P(s)$, i.e., $\{u_j, u_{j+1}\} \in V(P(s))$ for each $j \in \{1, \dots, q-1\}$. Since $i$ stays still, there is a prefix of $P(s)$ with agents that also stay still in step $s$. In other words, there is $r$, $1 \le r \le q$, such that the agents that occupy $u_1, \dots, u_r$ stay still in step $s$ while the agents that occupy $u_{r+1}, \dots, u_q$, if any, move. If $r = q$, i.e., no agents of the path move, then denote by $u_{q+1}$ the neighbor of $u_q$ that is closer to $pe(i)$ than $u_q$ (note that in this case $u_{q+1}$ holds no agent in step $s$ by the definition of $P(s)$). The agents that move, do move towards $pe(i)$. Since the other agents of $P(s)$ stay still, this may only happen when some other agent that is not present on $P(s)$ in step $s$ moves to $u_{r+1}$. We hence obtain that $|V(P(s+1))| > |V(P(s))|$ and $\nu_i(s) = \nu_i(s+1)$, which gives (2).

We note that the above movements of agents are not affected by the agents that are immobilized by Procedure DTE as dictated in line 5. This is because for each step $s$ considered above, the path $P(s)$ consists of vertices $x$ with $\mathrm{dist}(x, pe(i)) \le B$. This is because $P(s)$ is contained in the path between $pe(i)$ and $\nu_i(0)$ and by assumption $\mathrm{dist}(pe(i), \nu_i(0)) \le B$. We finally note that $\mathrm{dist}(\nu_i(0), pe(i)) \le B$, (2) and the fact that the loop of Procedure BoundedDTE in lines: 1-3 executes for $B$ steps together imply that within the first $\mathrm{dist}(pe(i), \nu_i(0))$ iterations of the loop the agent $i$ either evacuates or joins the group at $pe(i)$. $\square$

**Lemma 4.3.** If $t_{\mathrm{opt}} \le B$ and an executing agent $i$ has not evacuated within the first $B$ steps, then it evacuates during $4(B+t_{\mathrm{opt}})$ iterations of the second loop in Procedure BoundedDTE (lines: 5-7).

*Proof.* Consider an arbitrary agent $i$. We first observe that taking into account the exits in trees that are indirect descendants of $T_{\mathrm{pe}(i)}$ cannot shorten the evacuation time of agent $i$ who uses a strategy computed in line 4 of Procedure BoundedDTE. Let us assume for the moment that $i$ is not slowed down by other agents. We will justify this assumption just after the following paragraph. To the contrary assume that there exists such strategy and let $x_q$ be the secondary exit of $i$ in an indirect descendant $T_{x_q}$ of $T_{\mathrm{pe}(i)}$. Note that being an indirect descendant means that there exists $T_{x_p}$ with the exit $x_p$ such that $T_{x_q}$ is a descendant of $T_{x_p}$ and $T_{x_p}$ is a child of $T_{\mathrm{pe}(i)}$. So let us consider two paths: $P_1$ from $\nu_i(B)$ to $x_p$, and $P_2$ from $\nu_i(B)$ to $x_q$. Since there is the only edge $\{u, v\}$ with $u$ in $T_{\mathrm{pe}(i)}$ and $v$ in $T_{x_p}$, the paths $P_1, P_2$ have to share that edge. Consequently, the edge has to be traversed in any case and hence the considered agent $i$ can be directed to the exit $x_p$, instead of $x_q$, with no increase of its evacuation time, a contradiction.

In the above reasoning we used some indirect assumptions. Namely, we assumed that the agent $i$ moving from $\nu_i(B)$ to its secondary exit $se(i)$ in a child tree of $T_{\mathrm{pe}(i)}$, moves according to the principle of priority, i.e., it is not slowed down by other agents. In what follows we assume that the priority of any agent $i$ applies only in the child trees of $T_{\mathrm{pe}(i)}$. This, in particular, means that in $T_{\mathrm{pe}(i)}$, the agent $i$ has to give priority to any agent $j$ for which $T_{\mathrm{pe}(i)}$ is a child of $T_{\mathrm{pe}(j)}$ (note $se(j) = pe(i)$). We apply the above priority principle to all agents traversing child trees on their way to the secondary exits. The same reasoning applies, when an agent staying still (due to the condition in line 4 in Procedure DTE) is passed by the executing agent $i$. The above rules naturally extend to the groups of agents, which we will refer to later when analyzing group interactions.
Consider a group $\mathcal{G}_{\text{pe}(i)}(B)$. Let $t_{\text{evac}}(\mathcal{G}_{\text{pe}(i)}(B))$ denote the optimal evacuation time of the group $\mathcal{G}_{\text{pe}(i)}(B)$ according to the strategy computed in line 4 of Procedure BoundedDTE, and let $t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B))$ stand for the optimal evacuation time of that group through all possible exits in $T$ (note that in both cases, the strategies are locally optimal, and computed without information on other groups in $T$). Since according to the definition of the procedure, only the exits in the child trees can be used, and from the first part of the proof it follows that there is no need to use the exits in indirect descendant trees, the difference between $t_{\text{evac}}(\mathcal{G}_{\text{pe}(i)}(B))$ and $t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B))$ can only depend on the exits reachable through the parent tree of $T_{\text{pe}(i)}$.

More specifically, consider an optimal evacuation strategy $S_1$ for $\mathcal{G}_{\text{pe}(i)}(B)$ that takes the number of steps equal to $t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B))$. In the strategy $S_1$, let $\mathcal{G}'$ consist of those agents in $\mathcal{G}_{\text{pe}(i)}(B)$ who evacuated using only the exits reachable through the parent tree of $T_{\text{pe}(i)}$, and let $\mathcal{G}''$ consist of all agents who evacuated using the exits in the child trees of $T_{\text{pe}(i)}$ as well as the exit pe(i). Note that $\mathcal{G}' \cup \mathcal{G}'' = \mathcal{G}_{\text{pe}(i)}(B)$ and $\mathcal{G}' \cap \mathcal{G}'' = \emptyset$. Since $t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B)) = \max\{t(\mathcal{G}'), t(\mathcal{G}'')\}$, where $t(\mathcal{G}'), t(\mathcal{G}'')$ denote the evacuation times taken in $S_1$ by $\mathcal{G}'$ and $\mathcal{G}''$, respectively, it holds

$$t(\mathcal{G}') \le t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B)) \text{ and } t(\mathcal{G}'') \le t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B)). \qquad (3)$$

Moreover, since there is a unique edge between $T_{\text{pe}(i)}$ and its parent tree, each agent in $\mathcal{G}'$ has to traverse that edge. Hence

$$t(\mathcal{G}') \ge |\mathcal{G}'|. \qquad (4)$$

Now, consider a simple two-stage evacuation strategy $S_2$ that initially sets high priority to $\mathcal{G}'$ and applies a group swap within $\mathcal{G}_{\text{pe}(i)}(B)$ to allow the evacuation of $\mathcal{G}'$ through the exit pe(i) in at most $|\mathcal{G}'|$ steps. Next, in the second stage, $S_2$ uses $S_1$ to evacuate $\mathcal{G}''$ in at most $t(\mathcal{G}'')$ steps. Consequently,

$$t_{\text{evac}}(\mathcal{G}_{\text{pe}(i)}(B)) \le |\mathcal{G}'| + t(\mathcal{G}''). \qquad (5)$$

Applying (3) and (4), we conclude that restricting to only the exits in descendant trees, in the worst case doubles the evacuation time. More formally

$$t_{\text{evac}}(\mathcal{G}_{\text{pe}(i)}(B)) \le 2 t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B)). \qquad (6)$$

Recall that $\mathcal{A}_{\text{pe}(i)}$ denotes the set of agents with primary exits in pe(i). Consider the initial positioning (at the time instant 0) of agents belonging to $\mathcal{A}_{\text{pe}(i)}$, and let $t_{\text{opt}}^0(\mathcal{A}_{\text{pe}(i)})$ denote the optimal time of their offline evacuation starting from that positioning. Since $\mathcal{A}_{\text{pe}(i)}$ is a subset of the set of all agents, it holds

$$t_{\text{opt}}^0(\mathcal{A}_{\text{pe}(i)}) \le t_{\text{opt}}. \qquad (7)$$

Now, observe that any evacuation strategy for $\mathcal{A}_{\text{pe}(i)}$ that realizes (7) can be used to obtain a strategy for the group $\mathcal{G}_{\text{pe}(i)}(B)$. Indeed, let all agents of the group come back to their homebases by reversing the actions performed in lines 1–3 of Procedure BoundedDTE (which is possible in at most $B$ time units, then let them evacuate in at most $t_{\text{opt}}^0(\mathcal{A}_{\text{pe}(i)})$ time using the above-mentioned strategy for appropriate subgroup of $\mathcal{A}_{\text{pe}(i)}$). Consequently,

$$t_{\text{evac}}^T(\mathcal{G}_{\text{pe}(i)}(B)) \le B + t_{\text{opt}}^0(\mathcal{A}_{\text{pe}(i)}) \le B + t_{\text{opt}}. \qquad (8)$$

In the above analysis of $t_{\text{evac}}(\mathcal{G}_{\text{pe}(i)}(B))$, the presence of other groups and potential interactions and conflicts between them were not taken into account. Consequently, the time $t_{\text{evac}}(\mathcal{G}_{\text{pe}(i)}(B))$ computed for the group evacuation of $\mathcal{G}_{\text{pe}(i)}(B)$, may differ from $t_{\text{exec}}(\mathcal{G}_{\text{pe}(i)}(B))$ that is the time needed for the execution of Procedure BoundedDTE (lines: 5–7) for the same group.

Consider an arbitrary group $\mathcal{G}_x(B)$. In what follows, we analyze possible sources of conflicts between the groups and estimate how other groups influence $t_{\text{exec}}(\mathcal{G}_x(B))$. Namely, we prove that

$$t_{\text{exec}}(\mathcal{G}_x(B)) \le t_{\text{evac}}(\mathcal{G}_x(B)) + t_{\text{evac}}(\mathcal{G}_y(B)), \qquad (9)$$
where $y$ is the exit in the parent tree $T_y$ of the tree $T_x$.

First, let us consider the exit $x_r$ in the root tree $T_{x_r}$ and the following subgroups of agents:

$$ \mathcal{A}^{x_r} = \{j \in \mathcal{G}_{x_r}(B) \mid \text{pe}(j) = x_r \text{ and } \text{se}(j) = x_r\}, \quad (10) $$

$$ \mathcal{A}^{x_r z} = \{j \in \mathcal{G}_{x_r}(B) \mid \text{pe}(j) = x_r \text{ and } \text{se}(j) = z\}, \quad (11) $$

where exit $z$ belong to a child tree $T_z$ of $T_{x_r}$ (clearly there may be more than one subgroup of the second type, say one per each exit). As argued earlier, we restrict to the strategies that do not direct any agents to ancestor trees. Consequently, the execution time $t_{\text{exec}}(\mathcal{G}_{x_r}(B))$ cannot be affected by agents from descendant trees of $T_{x_r}$. Moreover, the groups $\mathcal{A}^{x_r z}$ are subject to the priority and hence for each of them $t_{\text{exec}}(\mathcal{A}^{x_r z}) = t_{\text{evac}}(\mathcal{A}^{x_r z}) \le t_{\text{evac}}(\mathcal{G}_{x_r}(B))$. Similarly, $t_{\text{exec}}(\mathcal{A}^{x_r}) = t_{\text{evac}}(\mathcal{A}^{x_r}) \le t_{\text{evac}}(\mathcal{G}_{x_r}(B))$. Thus taking maximum over all subgroups, we have

$$ t_{\text{exec}}(\mathcal{G}_{x_r}(B)) \le t_{\text{evac}}(\mathcal{G}_{x_r}(B)). \quad (12) $$

Now, consider $\mathcal{G}_x(B)$ at arbitrary primary exit $x$ such that $x \neq x_r$. Similarly as above, the group can be partitioned into subgroups defined analogously as (10) and (11). The evacuation of $\mathcal{G}_x(B)$ proceeds as in the previous case, with the difference that it can be affected by the agents from $\mathcal{A}^{yx}$ moving from the parent tree $T_y$ along $yx$-path to the secondary exit $x$ in $T_x$.

Since group swap or giving a way guarantee that the delay of $\mathcal{G}_x(B)$, caused by the priority of $\mathcal{A}^{yx}$ is not larger than $|\mathcal{A}^{yx}|$, it holds

$$ t_{\text{exec}}(\mathcal{G}_x(B)) \le t_{\text{evac}}(\mathcal{G}_x(B)) + |\mathcal{A}^{yx}|. \quad (13) $$

Now, it is enough to observe that since $\mathcal{A}^{yx} \subseteq \mathcal{G}_y(B)$, it holds $|\mathcal{A}^{yx}| \le t_{\text{evac}}(\mathcal{G}_y(B))$.

Thus, by (12) and (13) we conclude that (9) holds for all exits $x$.

Let $\mathcal{G}_{x^*}(B)$ be a group at exit $x^*$ such that

$$ t_{\text{exec}}(\mathcal{G}_{x^*}(B)) = \max\{x \in X \mid t_{\text{exec}}(\mathcal{G}_x(B))\}. \quad (14) $$

By (9), (6) and (8) we finally get

$$ \begin{aligned} t_{\text{exec}}(\mathcal{G}_{x^*}(B)) &\le t_{\text{evac}}(\mathcal{G}_{x^*}(B)) + t_{\text{evac}}(\mathcal{G}_y(B)) \\ &\le 2 t_{\text{evac}}^T(\mathcal{G}_{x^*}(B)) + 2 t_{\text{evac}}^T(\mathcal{G}_y(B)) \le 4(B + t_{\text{opt}}), \end{aligned} $$

where $T_y$ is the parent tree of $T_{x^*}$, when $x^* \neq x_r$.

□

Now, Lemma 4.1 follows directly from Lemmas 4.2 and 4.3.

It remains to bound the number of steps required by Procedure DTE.

**Theorem 4.2.** There exists a distributed evacuation strategy for arbitrary tree that completes in $\Theta(t_{\text{opt}})$ steps.

*Proof.* Let $t_{\text{DTE}}$ denote the number of steps required for the execution of Procedure DTE. Clearly, $t_{\text{DTE}}$ is finite, since during the execution of Procedure DTE, there is always a step in which the variable $B$ reaches a value greater than $t_{\text{opt}}$. Moreover, following the doubling rule we have $t_{\text{opt}} < B \le 2t_{\text{opt}}$. By Lemma 4.1 the number of steps needed for each of the subsequent values of $B$ is bounded from above by $9B$. Hence, altogether we get $t_{\text{DTE}} \le 18(2+4+\cdots+B) \le 36B \le 72t_{\text{opt}}$.

Considering agents' conflicts, observe that most issues have already been covered in the proofs of Lemmas 4.2 and 4.3. It remains to comment the reverse phase (see line 9). Namely, since any agent $i$ meeting the group moving in the opposite direction may be 'speeded up' by the group swap (compared to moving node-by-node), $i$ has to control the distance from its homebase
to ensure the right amount of time for the reverse phase. This is necessary due to the fact that some of those agents that speeded up $i$, may have already evacuated via their secondary exits and will not be present on $i$'s way during the reverse phase. Additionally, we assume that $i$ keeps priority while traversing back the nodes of a child tree of $T_{pe(i)}$. The argument is completed by observing that in the reverse phase, the number of agents that eventually slow down $i$ in $T_{pe(i)}$ cannot be larger than in the first phase (recall the upper bound $|A^{yx}|$ on the number of agents moving from the parent tree $T_y$ to the exit $x$ in $T_x$; see (13) in the proof of Lemma 4.3 and double counting of $9B$ (independently for the first and the reverse phase) in the first part of this proof). □

# 5 Generalizations of EVAC

In this section we introduce the problem RESTEVAC, a generalization of EVAC in which the moves of agents are restricted so that each agent has access to preselected subset of edges.

We start by defining an evacuation strategy in this scenario. All restrictions of EVAC carry over, except that additionally for each agent $i \in A$, a set $R_i \subseteq E(G)$ of permitted edges is given as a part of the input. Consequently, action (A1) defined in Section 2, is replaced by

(RA1) each agent either changes its location from the currently occupied node $v$ to one of its neighbors $u$ provided that $\{u, v\} \in R_i$, or the agent remains at $v$.

A strategy $(\nu_1, \dots, \nu_k)$ satisfying (RA1) and (A2) is called a restricted evacuation strategy. The decision version of our new problem, called RESTEVAC, is then defined as follows:

## RESTRICTED DISCRETE EVACUATION (RESTEVAC)

*Input:* A graph $G$, an integer $\ell$, a set $X$ of exits, a set $H$ of homebases occupied by $k$ agents, and sets $R_1, \dots, R_k$ specifying permitted edges.

*Question:* Does there exist a restricted evacuation strategy of length at most $\ell$?

## 5.1 The Complexity of RESTEVAC – Restricted Length

We now show that the RESTEVAC problem is NP-hard by a reduction from the 3-dimensional matching problem denoted by 3DM. We first recall the former problem. The input to 3DM consists of three pairwise disjoint $m$-element sets $A, B, C$ and a set of triples $M \subseteq A \times B \times C$. The answer to 3DM is YES if and only if there exists $M' \subseteq M$ such that $|M'| = m$ and for every two distinct triples $(a, b, c)$ and $(a', b', c')$ in $M'$ it holds $a \neq a', b \neq b'$ and $c \neq c'$.

**Theorem 5.1.** *The problem RESTEVAC is NP-complete even if the input parameter $\ell$ equals 2.*

*Proof.* We describe our reduction by constructing the input to RESTEVAC. Suppose that we have $(A, B, C, m, M)$ as the input to 3DM. For any triple $(a, b, c) \in M$ define for brevity $\xi((a, b, c)) = \{\{a, b\}, \{b, c\}\}$. Let $G$ be defined as follows:

$$G = \left( A \cup B \cup C, \bigcup_{Z \in M} \xi(Z) \right).$$

Set $\ell = 2$, $X = C$, $k = m$ and let the $k$ agents be initially placed on the nodes in $A$, i.e., set $H = A$. For each agent $i \in A$ having its homebase $a_i \in A$, let

$$R_i = \bigcup_{Z \in N} \xi(Z), \text{ where } N = M \cap (\{a_i\} \times B \times C).$$
This completes the construction and it remains to prove its correctness. We argue that the answer to 3DM is YES if and only if the answer to RESTEVAC is YES.

First, suppose that the answer to 3DM is YES and let $M' \subseteq M$ be the corresponding solution. We construct a restricted evacuation strategy $(\nu_1, \dots, \nu_k)$ as follows. For each $i \in A$ there exists $(a_i, b_i, c_i) \in M'$ and we define:

$$ \nu_i(0) = a_i, \quad \nu_i(1) = b_i, \quad \nu_i(2) = c_i. $$

It follows from the construction of the input to 3DM and from the definition of $X$ that $\nu_i(0) \neq \nu_j(0)$ for $i \neq j$. Since $M'$ is a solution to 3DM, we obtain that $\nu_i(s) \neq \nu_j(s)$ for $i \neq j$ and $s \in \{1, 2\}$. Consider an edge $e = \{\nu_i(s), \nu_i(s+1)\}$ traversed by agent $i$ in step $s \in \{0, 1\}$. We have that $e \in \xi((a_i, b_i, c_i))$ and hence $e \in R_i$. Finally, $\nu_i(2) \in X$ by construction for each $i \in A$, which proves that $(\nu_1, \dots, \nu_k)$ is indeed a restricted evacuation strategy of length 2.

Next, suppose that the answer to RESTEVAC is YES and let $(\nu_1, \dots, \nu_k)$ be a restricted evacuation strategy of length 2. Since the homebases of agents are in $A$ and $X = C$, we have that for each agent $i \in A$ it holds $\nu_i(0) \in A$, $\nu_i(1) \in B$ and $\nu_i(2) \in C$. Let us define the following set $M' = \{(\nu_i(0), \nu_i(1), \nu_i(2)) \mid i \in A\}$. We have that $\{\nu_i(0), \nu_i(1)\} \in R_i$ and $\{\nu_i(1), \nu_i(2)\} \in R_i$, which for each agent $i \in A$ implies $(\nu_i(0), \nu_i(1), \nu_i(2)) \in M$. Thus $M'$ is a solution to 3DM. $\square$

## 5.2 The Complexity of RESTEVAC – Two Types of Agents

We now prove that RESTEVAC is computationally hard even if there are only two types of agents, i.e., when there exist two subsets $E_1, E_2 \subseteq E(G)$ of permitted edges such that for each agent $i \in A$ it holds $R_i \in \{E_1, E_2\}$. Our proof is by a reduction from the problem (3,4)-SAT, in which a logical formula $F = C_1 \wedge C_2 \wedge \dots \wedge C_m$ over variables $x_1, \dots, x_p$ is a part of the input, where each clause $C_i$ is a disjunction of exactly three literals and each variable occurs at most four times in the logical formula. The question in (3,4)-SAT is whether there exists a Boolean assignment to variables that satisfies $F$. The problem (3,4)-SAT is known to be NP-complete [27]. The main result of this section is that RESTEVAC is computationally hard even for fixed length evacuation strategies and only two types of agents whose respective sets of permitted edges are disjoint.

**Theorem 5.2.** The problem RESTEVAC is NP-complete even if the input parameter $l$ equals 5 and for each agent $i \in A$ it holds $R_i \in \{E_1, E_2\}$, where $E_1 \cap E_2 = \emptyset$.

**Construction 5.1.** First, on the basis of formula $F$ and the integer $p$ we construct an input graph $G$ for the problem RESTEVAC. To that end we first define a variable component $G'$. Let the set of the nodes of the component $G'$ be given by

$$ V(G') = \{v_i^j | i \in \{0, \dots, 5\}, j \in \{1, 2\} \} \cup \{u_i^j | i \in \{1, \dots, 5\}, j \in \{1, 2\} \} \\ \cup \{x_{i,i'}^j, y_{i,i'}^j | i \in \{1, \dots, 4\}, i' \in \{0, \dots, 4\}, j \in \{1, 2\} \}, $$

where for convenience and brevity the following pairs of labels refer to the same nodes of $G'$: $u_5^1$ and $u_5^2$, $v_5^1$ and $v_5^2$, $x_{i,i}^j$ and $v_i^{3-j}$ for $i \in \{1, \dots, 4\}, j \in \{1, 2\}, y_{i,4}^1$ and $y_{i,4}^2$ for each $i \in \{1, \dots, 4\}$ (see also Figure 5). The edge set of $G'$ is given by $E(G') = R_1 \cup R_2$, where for $j \in \{1, 2\}$

$$ R_j = \{\{v_i^j, v_{i+1}^j\}, \{u_i^j, u_{i+1}^j\} | i \in \{1, \dots, 4\} \} \cup \{\{v_0^j, v_1^j\}, \{v_0^j, u_0^j\} \} \\ \cup \{\{x_{i,i'}^j, x_{i,i'+1}^j\}, \{y_{i,i'}^j, y_{i,i'+1}^j\} | i \in \{1, \dots, 4\}, i' \in \{0, \dots, 3\} \}. $$

For each $j \in \{1, 2\}$, we place agents at nodes $v_0^j$ and $x_{i,0}^j$, $i \in \{1, \dots, 4\}$ and we call them agents of type $j$. The set of permitted edges for agents of type $j$ is $R_j$, $j \in \{1, 2\}$. There are six exits
<figure><img src="image_6.png" /><figcaption>Figure 5: The variable component: squares are exits, dotted edges are in $R_1$ and dashed edges are in $R_2$, white nodes denote homebases of agents</figcaption></figure>

in the variable component: $u_5^1$, $v_5^1$ and $y_{1,4}^1, \dots, y_{4,4}^1$ (also denoted equivalently with upper index 2).

Having described the variable component, we continue the construction of our graph $G$, taking $p$ disjoint copies of the variable component, where the $c$-th copy, denoted by $G'_c$, corresponds to the variable $\mathbf{x}_c$, $c \in \{1, \dots, p\}$. To distinguish the nodes of the $c$-th copy of the variable component $G'_c$, $c \in \{1, \dots, p\}$, we write $x_{i,i'}^j(c)$, $y_{i,i'}^j(c)$, $v_i^j(c)$ and $u_i^j(c)$ in place of $x_{i,i'}^j$, $y_{i,i'}^j$, $v_i^j$ and $u_i^j$, respectively. In our construction of $G$, for each $m' \in \{1, \dots, m\}$ we add two nodes $f_1^{m'}$, $f_2^{m'}$ that correspond to the clause $C_{m'}$. Next, for each $m' \in \{1, \dots, m\}$ and $t \in \{1, 2, 3\}$ we follow the rules:

* if the $t$-th literal in $C_{m'}$ is $\mathbf{x}_c$ for some $c \in \{1, \dots, p\}$, then pick a single node among $x_{1,4}^1(c), \dots, x_{4,4}^1(c)$ and add to $G$ the edges connecting this node with $f_1^{m'}$ and $f_2^{m'}$,

* if the $t$-th literal in $C_{m'}$ is the negation of a variable $\mathbf{x}_c$, $c \in \{1, \dots, p\}$, then pick one node among $x_{1,4}^2(c), \dots, x_{4,4}^2(c)$ and add to $G$ edges connecting this node with $f_1^{m'}$ and $f_2^{m'}$.

Moreover, in the process of adding the above edges we have to ensure that each node $x_{i,4}^j(c)$, $i \in \{1, \dots, 4\}$, $j \in \{1, 2\}$ has at most one incident edge that does not belong to $G'_c$, $c \in \{1, \dots, p\}$. Initially we locate the agents in $G$ by placing them in variable components as described above (thus, we have $10p$ agents in total). If $z \in V(G)$ is the homebase of an agent, then such an agent is denoted by $\lambda(z)$. This completes the construction. Clearly, the construction might be computed in polynomial time. $\square$

We have the following observation that highlights the paths that each agent may take in any 5-step evacuation strategy.

**Observation 5.1.** For each $c \in \{1, \dots, p\}$, if the evacuation completes in 5 steps, then

(i) for each $j \in \{1, 2\}$, the agent $\lambda(v_0^j(c))$ traverses either the path $(v_0^j(c), \dots, v_5^j(c))$ or the path $(v_0^j(c), u_1^j(c), \dots, u_5^j(c))$,

(ii) for each $i \in \{1, \dots, 4\}$ and $j \in \{1, 2\}$, the agent $\lambda(x_{i,0}^j(c))$ traverses either the path $(x_{i,0}^j(c), y_{i,0}^j(c), \dots, y_{i,4}^j(c))$ or the path $(x_{i,0}^j(c), \dots, x_{i,5}^j(c), f_t^{m'})$ for some $t \in \{1, 2\}$ and $m' \in \{1, \dots, m\}$. $\square$
Note that instead of stating the paths that an agent can follow, one equivalently may provide
the node through which the agent evacuates. This equivalence is due to the construction of $G$,
namely from the fact that for each possible exit through which an agent may evacuate the path
of length 5 that leads to the exit is unique. The next observation states how the movements of
some agents affect the behavior of others.

**Observation 5.2.** For each $c \in \{1, \dots, p\}$, if the evacuation completes in 5 steps, then

(i) if the agent $\lambda(v_0^1(c))$ evacuates through $v_5^1(c)$ (respectively, $u_5^1(c)$), then the agent $\lambda(v_0^2(c))$ evacuates through $u_5^2(c)$ (respectively, $v_5^2(c)$),

(ii) for each $j \in \{1, 2\}$, the agent $\lambda(v_0^j(c))$ evacuates through $v_5^j(c)$ if and only if the agents $\lambda(x_{1,0}^j(c)), \dots, \lambda(x_{4,0}^j(c))$ evacuate through $y_{1,4}^j(c), \dots, y_{4,4}^j(c)$. $\square$

We now prove two main lemmas that essentially imply Theorem 5.2.

**Lemma 5.1.** Let $F$ and $\mathbf{x}_1, \dots, \mathbf{x}_p$ be the input to the (3,4)-SAT problem and let $G$ be the graph constructed above. If $F$ is satisfiable, then there exists a 5-step evacuation strategy in $G$.

*Proof.* Take a Boolean assignment to variables $\mathbf{x}_1, \dots, \mathbf{x}_p$ that satisfies $F$. We prescribe the movements of agents as follows. For each $c \in \{1, \dots, p\}$, if $\mathbf{x}_c$ is true, then:

* let the agent $\lambda(v_0^1(c))$ traverse the path $(v_0^1(c), u_1^1(c), \dots, u_5^1(c))$,

* let the agent $\lambda(v_0^2(c))$ traverse the path $(v_0^2(c), \dots, v_5^2(c))$,

* for each $i \in \{1, \dots, 4\}$, let the agent $\lambda(x_{i,0}^1(c))$ traverse the path $(x_{i,0}^1(c), y_{i,0}^1(c), \dots, y_{i,4}^1(c))$,

* for each $i \in \{1, \dots, 4\}$, let the agent $\lambda(x_{i,0}^2(c))$ traverse the path $(x_{i,0}^2(c), \dots, x_{i,5}^2(c), z)$, where $z$ is a node that corresponds to some clause.

For each $c \in \{1, \dots, p\}$, if $\mathbf{x}_c$ is false, then the agents perform the ‘opposite’ actions, namely:

* let the agent $\lambda(v_0^1(c))$ traverse the path $(v_0^1(c), \dots, v_5^1(c))$,

* let the agent $\lambda(v_0^2(c))$ traverse the path $(v_0^2(c), u_1^2(c), \dots, u_5^2(c))$,

* for each $i \in \{1, \dots, 4\}$, let the agent $\lambda(x_{i,0}^1(c))$ traverse the path $(x_{i,0}^1(c), \dots, x_{i,5}^1(c), z)$, where $z$ is a node that corresponds to some clause,

* for each $i \in \{1, \dots, 4\}$, let the agent $\lambda(x_{i,0}^2(c))$ traverse the path $(x_{i,0}^2(c), y_{i,0}^2(c), \dots, y_{i,4}^2(c))$.

This strategy does not specify the nodes $z$ that correspond to clauses and we will argue that
they can be selected to ensure that the evacuation strategy is valid. It immediately follows that
this strategy performs valid (i.e., collision free) movements of agents within the first four steps.
Thus, we analyze the last fifth step of the strategy. Any agent that is about to exit through a
node in a variable component can do so and thus it is enough to analyze the agents evacuating
through nodes that correspond to clauses. Thus, let $m' \in \{1, \dots, m\}$ be selected arbitrarily and
it is enough to argue that there exist at most two agents that in step 4 occupy nodes adjacent
to $f_1^{m'}$ and $f_2^{m'}$. Let $x_{i,4}^j(c)$, $c \in \{1, \dots, p\}$, $i \in \{1, \dots, 4\}$, $j \in \{1, 2\}$, be some neighbor of the
above nodes. Note that there exist exactly three nodes that belong to variable components and
are neighbors of $f_1^{m'}$ and $f_2^{m'}$. Hence, to complete the proof we show that if the literal in $C_{m'}$
that is $\mathbf{x}_c$ or its negation is true, then no agent occupies $x_{i,4}^j(c)$ in step 4. We now assume that
the literal is the variable and the proof is analogous for the case when the literal is the negation
of $\mathbf{x}_c$. We have that $j = 1$ according to the construction of $G$. Since $\mathbf{x}_c$ is true by assumption,
the agent $\lambda(x_{i,0}^1(c))$ traverses the path $(x_{i,0}^1(c), y_{i,0}^1(c), \dots, y_{i,4}^1(c))$ and therefore it is not present
at node $x_{i,4}^1$ in step 4. This completes the proof because no other agent can reach $x_{i,4}^1$. $\square$
**Lemma 5.2.** Let $F$ and $\mathbf{x}_1, \dots, \mathbf{x}_p$ be the input to the (3, 4)-SAT problem and let $G$ be the graph constructed above. If there exists a 5-step evacuation strategy in $G$, then $F$ is satisfiable.

*Proof.* We define Boolean assignment as follows: $\mathbf{x}_c$ is true if and only if the agent $\lambda(v_0^1(c))$ evacuates through $u_5^1(c)$ in the evacuation strategy, $c \in \{1, \dots, p\}$. Take any $m' \in \{1, \dots, m\}$ and we argue that some literal in $C_{m'}$ is true under the above assignment. The nodes $f_1^{m'}$ and $f_2^{m'}$ have three neighbors in variable components and therefore one of those variable components, say $G_c'$, has the property that the node of $G_c'$ adjacent to $f_1^{m'}$ and $f_2^{m'}$, let this node be $x_{i,4}^j(c)$, has no agent in step 4. The only agent that can reach $x_{i,4}^j(c)$ is $\lambda(x_{i,0}^j(c))$. By Observation 5.1, this agent evacuates through $y_{i,4}^j(c)$ in the evacuation strategy we consider. Thus, by Observations 5.1 and 5.2, the agent $\lambda(v_0^j)$ exists through $u_5^j(c)$. By construction of $G$, $C_{m'}$ has $\mathbf{x}_c$ as a literal if and only if $j=1$. If $j=1$, then by definition $\mathbf{x}_c$ is true and consequently $C_{m'}$ is true as required. If $j=2$, then by Observations 5.1 and 5.2, the agent $\lambda(v_0^1(c))$ evacuates through $v_5^1$ and therefore $\mathbf{x}_c$ is false, which implies that $C_{m'}$ is true. This completes the proof. $\square$

# 6 Conclusions and Open Problems

The goal of this work was to introduce a natural distributed model for the discrete evacuation problem and to analyze its basic properties by looking at its complexity and solvability in the mobile agent setting. One assumption that we made in this model, which greatly affects the algorithmic approach, is that local computations of agents and passing of messages take negligible time with respect to the movements of agents. However, one can consider scenarios in which the amount of communication performed in each synchronous step is somewhat more restricted. For example, one could analyze the number of messages exchanged by agents besides the evacuation time. As a different variation, one might consider some type of *look-compute-move* model.

Another research direction could lead towards dropping the assumption that the network is known to agents. In such scenario, an algorithmic approach should adopt some concepts from the well studied exploration problems for unknown networks. As an intermediate scenario, one could consider providing the agents only partial information about the network by performing, e.g., a quantitative analysis of the amount of input information (we refer here to the advice complexity introduced in [21]).

In terms of the competitive ratio achievable by any online algorithm, we studied tree networks, and it is interesting to see how this parameter would behave in other network topologies. For example, are there any networks for which the competitive ratio is not constant, e.g., a function of the number of agents or some other input parameter? Another open question is what happens when the agents cannot communicate but have only local visibility. We leave as an open problem what can be achieved in a distributed model by heterogeneous agents.

# References

[1] B. Alspach. Searching and sweeping graphs: a brief survey. *Le Matematiche (Catania)*, 59:5–37, 2004.

[2] G.N. Berlin. The use of directed routes for assessing escape potential. *Fire Technology*, 14(2):126–135, 1978. doi:10.1007/BF02308907.

[3] Piotr Borowiecki, Shantanu Das, Dariusz Dereniowski, and Łukasz Kuszner. Distributed evacuation in graphs with multiple exits. In *Structural Information and Communication Complexity - 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland,*
July 19-21, 2016, volume 9988 of Lecture Notes in Computer Science, pages 228-241, 2016. URL: https://doi.org/10.1007/978-3-319-48314-6_15, doi:10.1007/978-3-319-48314-6\_15.

[4] Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, and Roger Wattenhofer. Wireless evacuation on *m* rays with *k* searchers. *Theor. Comput. Sci.*, 811:56-69, 2020. doi:10.1016/j.tcs.2018.10.032.

[5] Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, and Roger Wattenhofer. Collaboration without communication: Evacuating two robots from a disk. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, *Algorithms and Complexity - 10th International Conference, CIAC 2017*, volume 10236 of *Lecture Notes in Computer Science*, pages 104-115, 2017. doi:10.1007/978-3-319-57586-5\_10.

[6] R.L. Breisch. An intuitive approach to speleotopology. *Southwestern Cavers*, 6:72-78, 1967.

[7] L.G. Chalmet, R.L. Francis, and P.B. Saunders. Network models for building evacuation. *Fire Technology*, 18(1):90-113, 1982. doi:10.1007/BF02993491.

[8] M. Chrobak, L. Gasieniec, T. Gorry, and R. Martin. Group search on the line. In *SOFSEM 2015*, volume 8939 of LNCS, pages 164-176, 2015. doi:10.1007/978-3-662-46078-8\_14.

[9] Serafino Cicerone, Gabriele Di Stefano, Leszek Gasieniec, and Alfredo Navarra. Asynchronous rendezvous with different maps. In Keren Censor-Hillel and Michele Flammini, editors, *Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L'Aquila, Italy, July 1-4, 2019, Proceedings*, volume 11639 of *Lecture Notes in Computer Science*, pages 154-169. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24922-9\_11, doi:10.1007/978-3-030-24922-9\_11.

[10] J. Czyżowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak. Evacuating robots via unknown exit in a disk. In *DISC 2014*, volume 8784 of LNCS, pages 122-136, 2014. doi:10.1007/978-3-662-45174-8\_9.

[11] Jurek Czyzowicz, Dariusz Dereniowski, Leszek Gasieniec, Ralf Klasing, Adrian Kosowski, and Dominik Pajak. Collision-free network exploration. *J. Comput. Syst. Sci.*, 86:70-81, 2017. URL: https://doi.org/10.1016/j.jcss.2016.11.008, doi:10.1016/J.JCSS.2016.11.008.

[12] Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Lata Narayanan, Jaroslav Opatrny, and Birgit Vogtenhuber. Evacuating robots from a disk using face-to-face communication. *Discret. Math. Theor. Comput. Sci.*, 22(4), 2020. URL: https://doi.org/10.23638/DMTCS-22-4-4, doi:10.23638/DMTCS-22-4-4.

[13] A. Avilés del Moral, M. Takimoto, and Y. Kambayashi. Distributed evacuation route planning using mobile agents. *Trans. Computational Collective Intelligence*, 17:128-144, 2014. doi:10.1007/978-3-662-44994-3\_7.

[14] Dariusz Dereniowski, Lukasz Kuszner, and Robert Ostrowski. Searching by heterogeneous agents. *J. Comput. Syst. Sci.*, 115:1-21, 2021. URL: https://doi.org/10.1016/j.jcss.2020.06.008, doi:10.1016/j.jcss.2020.06.008.

[15] Henri Devillez, Béni Egressy, Robin Fritsch, and Roger Wattenhofer. Two-agent tree evacuation. In Tomasz Jurdzinski and Stefan Schmid, editors, *Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Wrocław, Poland, June 28 - July 1, 2021, Proceedings*, volume 12810 of *Lecture Notes in Computer Science*, pages 204-221. Springer, 2021. doi:10.1007/978-3-030-79527-6\_12.
[16] Yann Disser and Sören Schmitt. Evacuating two robots from a disk: A second cut. In Keren Censor-Hillel and Michele Flammini, editors, *Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L’Aquila, Italy, July 1-4, 2019, Proceedings*, volume 11639 of *Lecture Notes in Computer Science*, pages 200–214. Springer, 2019. doi:10.1007/978-3-030-24922-9_14.

[17] J. Edmonds and R.M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. *J. ACM*, 19(2):248–264, 1972. doi:10.1145/321694.321699.

[18] Ashley Farrugia, Leszek Gasieniec, Łukasz Kuszner, and Eduardo Pacheco. Deterministic rendezvous with different maps. *J. Comput. Syst. Sci.*, 106:49–59, 2019. URL: https://doi.org/10.1016/j.jcss.2019.06.001, doi:10.1016/j.jcss.2019.06.001.

[19] L.R. Ford and D.R. Fulkerson. Constructing maximal dynamic flows from static flows. *Oper. Res.*, 6(3):419–433, 1958. doi:10.1287/opre.6.3.419.

[20] L.R. Ford and D.R. Fulkerson. *Flows in Networks*. Princeton University Press, Princeton, NJ, USA, 1962.

[21] P. Fraigniaud, D. Ilcinkas, and A. Pelc. Oracle size: a new measure of difficulty for communication tasks. In *PODC 2006*, pages 179–187. ACM, 2006.

[22] Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier, and Somnath Kundu. Evacuating from $l_p$ unit disks in the wireless model. *Theor. Comput. Sci.*, 944:113675, 2023. doi: 10.1016/j.tcs.2022.12.025.

[23] H.W. Hamacher and S.A. Tjandra. Mathematical Modelling of Evacuation Problems – A State of the Art. In *Pedestrian and Evacuation Dynamics*, pages 227–266, Berlin, 2002. Springer.

[24] Y. Higashikawa, M.J. Golin, and N. Katoh. Multiple sink location problems in dynamic path networks. *Theor. Comput. Sci.*, 607:2–15, 2015. doi:10.1016/j.tcs.2015.05.053.

[25] J.-P. Kappmeier. *Generalizations of flows over time with applications in evacuation optimization*. PhD thesis, Technische Universität Berlin, 2015.

[26] Debasish Pattanayak, H. Ramesh, Partha Sarathi Mandal, and Stefan Schmid. Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication. In Paolo Bellavista and Vijay K. Garg, editors, *Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, Varanasi, India, January 4-7, 2018*, pages 20:1–20:4. ACM, 2018. doi:10.1145/3154273.3154313.

[27] C.A. Tovey. A simplified NP-complete satisfiability problem. *Discr. Appl. Math.*, 8:85–89, 1984.