# Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of
Treelike Topology††thanks: This work was co-funded by the European Union under
the project Robotics and advanced industrial production (reg. no.
CZ.02.01.01/00/22_008/0004590). JMK was additionally supported by the Grant
Agency of the Czech Technical University in Prague, grant No.
SGS23/205/OHK3/3T/18. Furthermore, an extended abstract is accepted in AAAI
${}^{\prime}24$.

Foivos Fioravantes  Department of Theoretical Computer Science, Faculty of
Information Technology, Czech Technical University in Prague, Prague, Czech
Republic  Dušan Knop  Department of Theoretical Computer Science, Faculty of
Information Technology, Czech Technical University in Prague, Prague, Czech
Republic  Jan Matyáš Křišt́an  Department of Theoretical Computer Science,
Faculty of Information Technology, Czech Technical University in Prague,
Prague, Czech Republic  Nikolaos Melissinos  Department of Theoretical
Computer Science, Faculty of Information Technology, Czech Technical
University in Prague, Prague, Czech Republic  Michal Opler  Department of
Theoretical Computer Science, Faculty of Information Technology, Czech
Technical University in Prague, Prague, Czech Republic

###### Abstract

In the Multiagent Path Finding problem, we focus on efficiently finding non-
colliding paths for a set of $k$ agents on a given graph $G$, where each agent
seeks a path from its source vertex to a target. An important measure of the
quality of the solution is the length of the proposed schedule $\ell$, that
is, the length of a longest path (including the waiting time). In this work,
we propose a systematic study under the parameterized complexity framework.
The hardness results we provide align with many heuristics used for this
problem, whose running time could potentially be improved based on our fixed-
parameter tractability results.

We show that MAPF is [1]-hard with respect to $k$ (even if $k$ is combined
with the maximum degree of the input graph). The problem remains -hard in
planar graphs even if the maximum degree and the makespan $\ell$ are fixed
constants. On the positive side, we show an FPT algorithm for $k+\ell$.

As we delve further, the structure of $G$ comes into play. We give an
algorithm for parameter $k$ plus the diameter of the graph $G$. The MAPF
problem is [1]-hard for cliquewidth of $G$ plus $\ell$ while it is for
treewidth of $G$ plus $\ell$.

  * Keywords:

vertex-disjoint paths, motion planning, synchronised robots, multiagent,
pathfinding.

##  1 Introduction

In this paper, we study the Multiagent Path Finding (MAPF) problem. MAPF has
many real-world applications, e.g., in warehouse management [33, 17], airport
towing [21], autonomous vehicles, robotics [32], digital entertainment [20],
and computer games [25]. In MAPF the task is to find non-colliding paths for a
set of $k$ agents on a given graph $G$, where each agent seeks a path from its
source vertex to a target.

This important problem has been, to the best of our knowledge, formally
introduced about 20 years ago and attracted many researchers since then.
Nowadays, there are numerous variants of the formal model for the problem; see
[27]. It is not surprising that the MAPF problem is in general -complete [28];
the hardnes holds even in planar graphs [34]. Therefore, there are numerous
heuristic approaches that allow us to efficiently obtain a useful solution for
the given input; see, e.g., the survey [26] for overview of such results. A
multitude of techniques was used to tackle MAPF—A*-based algorithms [13], SAT-
based algorithms [31], scheduling approach [2], SMT-solvers [29, 30], to name
just a few. Our work focuses on exact algorithms, that is, the aim is to
return an optimal solution and the central question is on which kinds of
inputs this can be done in an efficient way and where this is unlikely. While
doing so, we initiate parameterised analysis of the Multiagent Path Finding
problem with the focus on natural and structural parameters. Note that the
MAPF problem features two natural parameters—the number of agents $k$ and the
total length of the schedule $\ell$ (also called _makespan_). It is worth
noting that two versions of MAPF are usually studied in the literature—one
allows swapping two agents along an edge while this is prohibited in the
other. Roughly speaking, the first version treats the input topology as a
bidirected graph while the other as undirected. Most of our algorithmic
results are independent of allowing or forbidding swaps; therefore, we reserve
the name Multiagent Path Finding for the version where we do not care about
swaps. If the result holds only with swaps allowed, we use Multiagent Path
Finding Swaps to refer to that specific version fo the problem while we use
Multiagent Path Finding No Swaps for the version where we explicitly do not
allow swaps.

### Our Contribution

It is well-known that MAPF can be reduced to a shortest-path problem in a
graph known as the $k$-agent search space. Then, one can apply any algorithm
to find a shortest path in this graph to find a solution to the original
problem, e.g., using A*. The main downside of this approach is the size of the
search space. We first show that it is unlikely to desing an efficient pruning
algorithm for the $k$-agent search space:

######  Theorem 1.

The Multiagent Path Finding problem is [1]-hard parameterised by the number of
agents $k$ plus $\Delta(G)$ the maximum degree of the graph $G$.

Indeed, the above observation yields the following.

######  Theorem 2.

The Multiagent Path Finding problem is in parameterised by the number of
agents $k$.

We continue the study of classical complexity of MAPF with focus on the
structure of the input graph $G$. Driven by some applications, one is
interested in specific graph classes such as planar graphs or trees. Sadly, we
show that the MAPF problem remains intractable in both these graph classes
even if some other parts of the input are fixed constants.

######  Theorem 3.

The Multiagent Path Finding Swaps problem remains -complete even if the input
graph $G$ is planar, $\ell=3$, and $\Delta(G)=4$.

It was known [19] that Multiagent Path Finding is -complete when $\ell=3$ (in
general graphs). The -hardness for planar graphs [34] was recently improved to
constant degree [8]; there $\ell=26$ and $\Delta(G)=4$. However, Theorem 3
features all three of these properties. Furthermore, we believe that our
reduction is simpler than the one of Eiben et al. It is not hard to see that
instance with makespan $2$ and swaps are allowed can be solved in polynomial
time via a reduction to Hall’s Marriage Theorem (which is used to find
suitable middle point of all of the paths from sources to destinations). Thus,
with the above theorem we get a tight dichotomy result in classical
complexity.

Moreover we observe that, surprisingly, when swapping is not allowed, the
problem becomes hard even for $\ell=2$. Note that for $\ell=1$ it is trivial.

######  Theorem 4.

The Multiagent Path Finding No Swaps problem remains -complete even if the
input graph $G$ is planar, $\ell=2$ and $\Delta(G)=5$.

The proof of Theorem 4 is achieved by slightly adjusting the gadgets used in
the proof of Theorem 3.

######  Theorem 5.

The Multiagent Path Finding No Swaps problem remains -complete even if $G$ is
a tree of maximum degree $\Delta(G)=5$.

Note that the Multiagent Path Finding Swaps was recently shown to be -complete
for the case where the imput graph is a tree and the number of agents is equal
to the number of vertices of that tree [1]. Our Theorem 5 differs from this
work as, apart from treating the non-swapping version, it also tackles the
problem for an arbitrary number of agents.

At this point, we see that none of the standard parameters—$k$ or $\ell$—is a
good parameter alone. We complement this by showing that the combination of
the two parameters results in fixed-parameter tractability.

######  Theorem 6.

The Multiagent Path Finding problem is in parameterised by the number of
agents $k$ plus the makespan $\ell$.

In the rest of the paper, we seek a good structural companion parameters to
either of these. We begin with a very restrictive parameter—the vertex cover
number that constitutes a rather simple starting point for our more general
results. Here, we exploit the fact that many agents behave in a same way,
i.e., they are almost anonymous. Furthermore, we can prune the input graph
$G$, so that its size is bounded in terms of parameters (i.e., we provide a
kernel).

######  Theorem 7.

The Multiagent Path Finding problem is in parameterised by the number of
agents $k$ plus the vertex cover number $\operatorname{vc}(G)$.

It is known, that graphs of bounded vertex cover number have bounded
diameter—the length of a longest shortest path in the graph (in a connected
component). We strengthen the above result by proving that diameter is a
strong companion to $k$. Note that this yields tractability for many
structural parameters including MIM-width as it implies bounded diameter. The
proof uses the fact that if a graph has many vertices (unbounded in terms of
$k$ and the diameter) and small dimater, it must contain a vertex of large
degree. We use such a vertex as a hub and prove that if we first route all
agents to the neighborhood of that vertex and then to their respective
destinations, we obtain routes with makespan $O(k\cdot d)$, where $d$ is the
diameter. The theorem then follows from Theorem 6.

######  Theorem 8.

The MAPF problem is in parameterised by the number of agents $k$ plus the
diameter of $G$.

Note that the vertex cover number $\operatorname{vc}(G)$ also bounds the
number of agents that can move simultaneously. This can be generalized to a
number of locally moving agents or, in other words, the size of separators in
$G$. It is well-known that the size of vertex separators in a graph is related
to a graph parameter treewidth. However, in view of our Theorem 5, there is
little hope to conceive an efficient algorithm parameterized just by the
treewidth of the input graph. To remedy this, we additionally parameterize by
$\ell$ to get tractability of MAPF.

######  Theorem 9.

The Multiagent Path Finding problem is in parameterised by the treewidth
$\operatorname{tw}(G)$ plus the makespan $\ell$.

Cliquewidth is a parameter further generalizing both vertex cover number and
treewidth [5]. However, the same additional parameterization as above leads
here to intractability.

######  Theorem 10.

The Multiagent Path Finding problem is in [1]-hard parameterised by the
cliquewidth $\operatorname{cw}(G)$ plus the makespan $\ell$.

##  2 Preliminaries

For integers $m$ and $n$, we denote $[m:n]$ the set of all integers between
$m$ and $n$, that is, $[m:n]=\\{m,m+1,\ldots,n\\}$. We use $[n]$ as a
shorthand for $[1:n]$.

Formally, in the Multiagent Path Finding problem we are given a graph
$G=(V,E)$, a set of agents $A$, a positive integer $\ell$, and two functions
$s_{0}\colon A\rightarrow V$ and $t\colon A\rightarrow V$ such that for any
pair $a,b\in A$ where $a\neq b$, $s_{0}(a)\neq s_{0}(b)$ and $t(a)\neq t(b)$.
Initially, each agent $a\in A$, is placed on the vertex $s_{0}(a)$. At
specific times, called turns, the agents are allowed to move to a neighboring
vertex, but are not obliged to do so. The agents can make at most one move per
turn and each vertex can host at most one agent at a given turn. The position
of the agents in the end of turn $i$ (after the agents have moved) is given by
a function $s_{i}\colon A\rightarrow V$.

We consider two versions of the problem; in Multiagent Path Finding Swaps
(MAPFS) we allow _swaps_ , _i.e._ , two agents to move through the same edge
during the same turn, while in Multiagent Path Finding No Swaps (MAPFNS) we do
not allow swaps. In the first case, given $s_{i-1}(a)$ for every agent $a\in
A$, _i.e._ , the positions of the agents at the turn $i-1$, the positions
$s_{i}$ are considered _feasible_ if $s_{i}(a)$ is a neighbor of $s_{i-1}(a)$
in $G$, for every agent $a\in A$. In the second case, the positions $s_{i}$
are feasible if, in addition to the previous, there is no pair of agents
$a,b\in A$ such that $s_{i}(a)=s_{i-1}(b)$ and $s_{i}(b)=s_{i-1}(a)$.

We say that a sequence $s_{1},\ldots,s_{\ell}$ is a solution of $\langle
G,A,s_{0},t,\ell\rangle$ if $s_{i}$ is considered feasible for all
$i\in[\ell]$ and $s_{\ell}=t$. Also, a feasible solution
$s_{1},\ldots,s_{\ell}$ has _makespan_ $\ell$. Our goal is to decide if there
exists a solution of makespan $\ell$.

#### Parametrized Complexity.

Parametrized complexity is a computational paradigm that extends classical
measures of time (and space) complexity, aiming to examine the computational
complexity of problems with respect to a secondary measure—the parameter.
Formally, a parameterized problem is a set of instances
$(x,k)\in\Sigma^{*}\times\mathbb{N}$, where $k$ is called the parameter of the
instance. A parameterized problem is _fixed-parameter tractable_ if it can be
determined in $f(k)\cdot\operatorname{poly}(|x|)$ time for an arbitrary
computable function $f\colon\mathbb{N}\to\mathbb{N}$. Such a problem then
belongs to the class . A parameterized problem is _slicewise polynomial_ if it
can be determined in $|x|^{f(k)}$ time for a computable function
$f\colon\mathbb{N}\to\mathbb{N}$. Such a problem then belongs to the class . A
problem is presumably not in  if it is shown to be [1]-hard (by a
parameterized reduction). We refer the interested reader to now classical
monographs [6, 23, 9, 7] for a more comprehensive introduction to this topic.

#### Structural Parameters.

Let $G=(V,E)$ be a graph. A set $U\subseteq V$ is a _vertex cover_ if for
every edge $e\in E$ it holds that $U\cap e\not=\emptyset$. The _vertex cover
number_ of $G$, denoted $\operatorname{vc}(G)$, is the minimum size of a
vertex cover of $G$.

A _tree-decomposition_ of $G$ is a pair $(\mathcal{T},\beta)$, where
$\mathcal{T}$ is a tree rooted at a node $r\in V(\mathcal{T})$, $\beta\colon
V(\mathcal{T})\to 2^{V}$ is a function assigning each node $x$ of
$\mathcal{T}$ its _bag_ , and the following conditions hold:

    * –

for every edge $\\{u,v\\}\in E(G)$ there is a node $x\in V(\mathcal{T})$ such
that $u,v\in\beta(x)$ and

    * –

for every vertex $v\in V$, the set of nodes $x$ with $v\in\beta(x)$ induces a
connected subtree of $\mathcal{T}$.

The _width_ of a tree-decomposition $(\mathcal{T},\beta)$ is $\max_{x\in
V(\mathcal{T})}|\beta(x)|-1$, and the treewidth $\operatorname{tw}(G)$ of a
graph $G$ is the minimum width of a tree-decomposition of $G$. It is known
that computing a tree-decomposition of minimum width is fixed-parameter
tractable when parameterized by the treewidth [15, 3], and even more efficient
algorithms exist for obtaining near-optimal tree-decompositions [16].

Cliquewidth is a prominent parameter that generalizes treewidth [5].
Cliquewidth corresponds to an algebraic expression describing the graph (i.e.,
how the graph is created from labeled vertices). We can use (1) introducing a
single vertex of any label, (2) disjoint union of two lebeled graphs, (3)
introducing edges between _all_ pair of vertices of two labels, and (4)
changing the label of _all_ vertices of a given label (i.e., collapsing a pair
of labels). An expression describes a graph $G$ if $G$ the final graph given
by the expression (after we remove all the labels). The _width_ of an
expression is the number of labels it uses. The cliquewidth of a graph is the
minimum width of an expression describing it.

##  3 FPT Algorithms

For all the results presented in this section, we give a precise running time
which was not given in the introduction.

###  3.1 Bounded number of agents plus makespan

Let $G=(V,E)$ be an undirected graph and $\ell$ a positive integer. We capture
the movement of agents through $G$ via a directed graph with vertices
representing positions in both place and time. A _time-expanded graph of $G$
with respect to $\ell$_, denoted $G_{T}(\ell)$, is a directed graph with one
copy of each vertex $v\in V$ for each time step $i\in[0:\ell]$, i.e., its
vertex set is $\\{v_{j}\mid v\in V,j\in[0:\ell]\\}$. The set of vertices
$\\{v_{j}\mid v\in V\\}$ for any fixed $j$, is called a _layer_. For every
edge $\\{u,v\\}\in V$ and every $i\in[\ell]$, the graph $G_{T}(\ell)$ contains
two arcs $(u_{i-1},v_{i})$ and $(v_{i-1},u_{i})$. Moreover for each vertex
$v\in V$ and $i\in[\ell]$, the graph $G_{T}(\ell)$ contains an arc
$(v_{i-1},v_{i})$. Vertex-disjoint paths in $G_{T}(\ell)$ capture exactly the
valid movements of agents when swaps are allowed.

We also introduce a modified version of this graph for the swap-free version
of Multiagent Path Finding. A _swap-free time-expanded graph of $G$ with
respect to $\ell$_, denoted $G^{\star}_{T}(\ell)$, is a directed graph
consisting of $2\ell+1$ layers, that we again distinguish using subscripts. It
contains a copy $v_{i}$ of vertex $v\in V$ for every $i\in[0:2\ell]$. Moreover
$G^{\star}_{T}(\ell)$ contains a vertex $e_{2i-1}$ for every edge $e\in E$ and
every $i\in[\ell]$. Similarly to $G_{T}(\ell)$, $G^{\star}_{T}(\ell)$ contains
an arc $(v_{i-1},v_{i})$ for every vertex $v\in V$ and every $i\in[2\ell]$.
And finally for every edge $e=(u,v)$ in $E$ and every $i\in[\ell]$, there are
four arcs $(u_{2i-2},e_{2i-1})$, $(v_{2i-2},e_{2i-1})$, $(e_{2i-1},u_{2i})$
and $(e_{2i-1},v_{2i})$ in $G^{\star}_{T}(\ell)$. Again, it is straightforward
to see that vertex-disjoint paths in $G^{\star}_{T}(\ell)$ capture exactly the
valid movements of agents when swaps are disallowed.

(a) $G$.

(b) $G_{T}(3)$.

(c) $G^{\star}_{T}(3)$. The black vertices correspond to the edges of $G$.

Figure 1: An example of a graph $G$, together with $G_{T}(3)$ and
$G^{\star}_{T}(3)$.

######  Observation 1.

Let $\mathcal{I}=\langle G,A,s_{0},t,\ell\rangle$ be an instance of MAPF. Then
$\mathcal{I}$ is a yes-instance of MAPFS (MAPFNS resp.) if and only if there
exists a set of directed pairwise vertex-disjoint paths in $G_{T}(\ell)$
($G^{\star}_{T}(\ell)$ resp.) connecting all pairs
$\\{(s_{0}(a)_{0},t(a)_{\ell})\mid a\in A\\}$
($\\{(s_{0}(a)_{0},t(a)_{2\ell})\mid a\in A\\}$ resop.), where the second
index is used to denote the corresponding layer of $G_{T}(\ell)$
($G^{*}_{T}(\ell)$ resp.).

######  Theorem 11.

The Multiagent Path Finding problem can be solved by an FPT-algorithm
parameterised by the number of agents $k$ plus the makespan $\ell$ in
$O(2^{O(k\cdot\ell)}\cdot m\cdot\log n)$ time.

###### Proof.

We reduce to the Bounded Vertex Directed Multi-terminal disjoint Paths (BVDMP)
problem. Its input consists of a directed graph $G$, two positive integers
$k,d$, and $k$ pairs of vertices $\\{(s_{i},t_{i})\mid i\in[k]\\}$ in $G$; and
the task is to decide whether there is a set of $k$ directed vertex-disjoint
paths of length at most $d$ connecting all pairs $\\{(s_{i},t_{i})\mid
i\in[k]\\}$. The BVDMP problem can be solved by an FPT-algorithm parameterised
by $k$ plus $d$ in $O(2^{O(k\cdot d)}\cdot m\cdot\log n)$ time [12].

Let $\langle G,A,s_{0},t,\ell\rangle$ be an instance of MAPF. Due to
Observation 1, it is sufficient to test whether there exists a set of $k$
directed pairwise vertex-disjoint paths either in $G_{T}(\ell)$ or in
$G^{\star}_{T}(\ell)$ depending on whether we allow swaps or not. Notice that
such paths have length exactly $\ell$ in $G_{T}(\ell)$ and $2\ell$ in
$G_{T}^{\star}(\ell)$. Thus for MAPFS, it suffices to invoke the FPT algorithm
for BVDMP on the graph $G_{T}(\ell)$ with the pairs of vertices
$\\{(s_{0}(a)_{0},t(a)_{\ell})\mid a\in A\\}$ and setting $d=\ell$. While for
MAPFNS, we run the same algorithm on the graph $G^{\star}_{T}(\ell)$ with the
pairs of vertices $\\{(s_{0}(a)_{0},t(a)_{2\ell})\mid a\in A\\}$ and
$d=2\ell$. The resulting algorithms run in $O(2^{O(k\cdot\ell)}\cdot
m\cdot\log n)$ time since both $G_{T}(\ell)$ and $G_{T}^{\star}(\ell)$ have
$O(\ell\cdot m)$ edges. ∎

###  3.2 Bounded treewidth plus makespan

######  Lemma 1.

For an undirected graph $G$ and a non-negative integer $p$, the treewidth of
both graphs $G_{T}(\ell)$ and $G^{\star}_{T}(\ell)$ is at most
$O(\ell\cdot\operatorname{tw}(G))$.

###### Proof.

Let $(T,\beta)$ be a tree decomposition of $G=(V,E)$ of optimal width. First,
let us consider the graph $G_{T}(\ell)$. Let $(T,\beta^{\prime})$ be the tree
decomposition obtained by replacing every occurrence of a vertex $v$ in any
bag with its $\ell+1$ copies $v_{0},\dots,v_{\ell}$. Clearly,
$|\beta^{\prime}(x)|=(\ell+1)\cdot|\beta(x)|$ for every node $x$ and it is
easy to check that all the properties of tree decompositions hold.

Now, let us consider $G_{T}^{\star}(\ell)$. We first modify the tree
decomposition $(T,\beta)$ into $(T^{\prime},\beta^{\prime})$ such that each
edge $e$ has a unique associated node $x^{\prime}_{e}$ in $T^{\prime}$ such
that both endpoints of $e$ lie in $\beta^{\prime}(x^{\prime}_{e})$. That is
easily achieved by first choosing an arbitrary such node $x_{e}$ for each edge
and then creating its new copy $x^{\prime}_{e}$ attached to $x_{e}$ as a leaf.
We construct a tree decomposition $(T^{\prime\prime},\beta^{\prime\prime})$ of
$G_{T}^{\star}(\ell)$ by the following modification of
$(T^{\prime},\beta^{\prime})$. As before, we replace every occurrence of a
vertex $v$ in any bag with its $2\ell+1$ copies $v_{0},\dots,v_{2\ell}$.
Moreover, for each edge $e\in E$, we add the vertices
$e_{1},e_{3},\dots,e_{2\ell-1}$ to the bag
$\beta^{\prime\prime}(x^{\prime}_{e})$. Observe that
$|\beta^{\prime\prime}(x)|\leq(2\ell+1)\cdot|\beta(x)|+\ell$ for every node
$x$ in $T^{\prime\prime}$. It is again straightforward to verify the required
properties of tree decompositions. ∎

######  Theorem 12.

The Multiagent Path Finding problem can be solved by an FPT-algorithm
parameterised by the treewidth $w$ of $G$ plus the makespan $\ell$ in
$(\ell\cdot w)^{O(\ell\cdot w)}\cdot n$ time.

###### Proof.

Let $\langle G,A,s_{0},t,\ell\rangle$ be an instance of MAPF. First, let us
consider the variant MAPFS where swaps are allowed. Due to Observation 1, it
suffices to check whether there exists a set of directed pairwise vertex-
disjoint paths in $G_{T}(\ell)$ connecting all pairs
$\\{(s_{0}(a)_{0},t(a)_{\ell})\mid a\in A\\}$. Moreover by Lemma 1, the
treewidth of $G_{T}(\ell)$ is at most $O(\ell\cdot\operatorname{tw}(G))$.
Finding vertex-disjoint paths in a directed graph $G_{T}(\ell)$ is in FPT
parameterised by the treewidth $G_{T}(\ell)$ via a simple modification of the
undirected case [24] accounting for the orientation of the arcs. The algorithm
runs in $(w^{\prime})^{O(w^{\prime})}\cdot n$ time, where $w^{\prime}$ is the
treewidth of $G_{T}(\ell)$. Thus, we can solve the Multiagent Path Finding
problem in $(\ell\cdot w)^{O(\ell\cdot w)}\cdot n$ time, where $w$ is the
treewidth of $G$.

For the swap-free variant MAPFNS, the algorithm follows via the same argument
simply by using the swap-free time-expanded graph $G_{T}^{\star}(\ell)$
instead of $G_{T}(\ell)$. Observe that $G_{T}^{\star}(\ell)$ has
$O(\ell\cdot(n+m))$ vertices and $O(\ell\cdot(n+m))$ edges where $n$, $m$ is
the number of vertices and edges in $G$, respectively. However, we can bound
$m$ by $O(w\cdot n)$ since graphs of bounded tree-width are sparse [15] and
thus the asymptotic bound on the runtime remains unchanged. ∎

###  3.3 Bounded number of agents plus vertex cover number

######  Theorem 13.

The Multiagent Path Finding problem, admits a kernel of size
$O(2^{\operatorname{vc}}k)$, where $\operatorname{vc}$ is the size of a
minimum vertex cover of the given graph and $k$ the number of agents.

###### Proof.

Let $\langle G,A,s_{0},t,\ell\rangle$ be an instance of MAPF problem and
$U\subseteq V(G)$ be a minimum vertex cover of $G$. For each subset $S\subset
U$, let $V_{S}$ denote the subset of $V(G)\setminus U$ where $v\in V_{S}$ if
and only if $N(v)=S$. Notice that any pair of vertices $u,v$ that belong in
the same set $V_{S}$ , for some $S\subset U$, are twins. For each $S$, we
select a _representative_ set of vertices $U_{S}$, defined as follows: if
$|V_{S}|\leq 3k$ then $U_{S}=V_{S}$, otherwise we select a $U_{S}$ that
satisfies the following properties:

    * –

$U_{S}\subseteq V_{S}$,

    * –

$U_{S}\supseteq V_{S}\cap\\{s_{0}(a),t(a)\mid a\in A\\}$ and

    * –

$|U_{S}\setminus\\{s_{0}(a),t(a)\mid a\in A\\}|=k$.

There are enough vertices to add so that the last property is satisfied since
$|\\{s_{0}(a),t(a)\mid a\in A\\}|\leq 2k$ and $|V_{S}|>3k$. Also, any set that
satisfies these conditions has size at most $3k$. Now, we create the new
instance of MAPF as follows. First, we create $H$, the induced subgraph of $G$
where $H=G[U\cup\bigcup_{S\subseteq U}U_{S}]$. The new instance has the same
set of agents, with the same starting and terminal positions as the original
one. This gives us a new instance $\langle H,A,s_{0},t,\ell\rangle$, where
$|V(H)|=|U\cup\bigcup_{S\subseteq
U}U_{S}|=\operatorname{vc}+2^{\operatorname{vc}}3k$. We will show that the two
instances are equivalent.

Since $H$ is an induced subgarph of $G$, any feasible solution in $H$ is also
a feasible solution in $G$. Therefore, if $\langle H,A,s_{0},t,\ell\rangle$ is
a yes-instance, this is also true for $\langle G,A,s_{0},t,\ell\rangle$. Next,
we show that any feasible solution of $\langle G,A,s_{0},t,\ell\rangle$ can be
transformed into a feasible solution of $\langle H,A,s_{0},t,\ell\rangle$. Let
$s_{1},\ldots,s_{\ell}$ be a feasible sequence for $\langle
G,A,s_{0},t,\ell\rangle$. We create a sequence
$s_{1}^{\prime},\ldots,s_{\ell}^{\prime}$ for $\langle
H,A,s_{0},t,\ell\rangle$ inductively.

In particular, we will create a sequence
$s_{1}^{\prime},\ldots,s_{\ell}^{\prime}$ where, for any $i\in[\ell]$ and
agent $a\in A$, the following holds:

    * –

if $s_{i}(a)\in U\cup\\{s_{0}(a),t(a)\mid a\in A\\}$ then
$s_{i}^{\prime}(a)=s_{i}(a)$,

    * –

otherwise, $s_{i}^{\prime}(a)\in U_{S}$ where $S=N_{G}(s_{i}(a))$.

We start the construction with $s_{1}^{\prime}$. First we partition the agent
set $A$ in to two sets $A_{1}$ and $A_{2}$ where $a\in A_{1}$ if $s_{1}(a)\in
V(H)$ and $a\in A_{2}$ otherwise. For any agent $a\in A_{1}$ we set
$s_{1}^{\prime}(a)=s_{1}(a)$. Then, we select an agent $b\in A_{2}$; let
$s_{1}(b)=v$ and $S=N_{G}(b)$. We are selecting a vertex $u\in U_{S}$ such
that $u\neq s_{1}(a)$ for any $a\in A_{1}$. We set $s_{1}^{\prime}(b)=u$ and
we move $b$ form $A_{2}$ to $A_{1}$. Notice that, since $v\notin V(H)$, we
have enough vertices in $U_{S}\setminus\\{s_{0}(a),t(a)\mid a\in A\\}$ to
achieve this. We repeat until $A_{2}$ is empty.

All the moves described by $s_{1}^{\prime}$ are valid in $H$. Indeed, notice
that for any agent $a\in A$ such that $s_{1}^{\prime}(a)=s_{1}(a)$, this move
is obviously valid as it was valid in $G$. Also, for any other agent the move
is also valid because the selected $s_{1}^{\prime}(a)$ is a twin of
$s_{1}(a)$. Finally, notice that for any agent $a\in A$ such that
$s_{1}^{\prime}(a)\neq s_{1}(a)$, neither of $s_{1}^{\prime}(a)$ and
$s_{1}(a)$ belong to $U\cup\\{s_{0}(b),t(b)\mid b\in A\\}$.

Assume now that we have created the sub-sequence
$s_{1}^{\prime},\ldots,s_{i}^{\prime}$ for some $i<\ell$, all moves between
$s_{j-1}^{\prime}$ and $s_{j}^{\prime}$ are valid for any $j\in[i]$ and that
for any $j\in[i]$ and agent $a\in A$,

    * –

if $s_{j}(a)\in U\cup\\{s_{0}(a),t(a)\mid a\in A\\}$ then
$s_{j}^{\prime}(a)=s_{j}(a)$,

    * –

otherwise, $s_{j}^{\prime}(a)\in U_{S}$ where $S=N_{G}(s_{j}(a))$.

We create $s_{i+1}^{\prime}$ using $s_{i+1}$, $s_{i}$ and $s_{i}^{\prime}$. We
start by partitioning $A$ in to three sets $A_{1}$, $A_{2}$ and $A_{3}$ such
that:

    * –

$A_{1}=\\{a\in A\mid s_{i+1}(a)\in U\cup\\{s_{0}(b),t(b)\mid b\in A\\}\\}$,

    * –

$A_{2}=\\{a\in A\setminus A_{1}\mid s_{i+1}(a)=s_{i}(a)\\}$,

    * –

$A_{3}=A\setminus(A_{1}\cup A_{2})$.

For any agent $a\in A_{1}$, we set $s_{i+1}^{\prime}(a)=s_{i+1}(a)$. For any
agent $a\in A_{2}$, we set $s_{i+1}^{\prime}(a)=s_{i}^{\prime}(a)$. We create
an empty set $B$. Then we select an agent $b\in A_{3}\setminus B$; let
$s_{i+1}(b)=v$ and $S=N_{G}(v)$. We select a vertex $u\in
U_{S}\setminus\\{s_{0}(a),t(a)\mid a\in A\\}$ such that $u\neq
s_{i+1}^{\prime}(a)$ for any $a\in A_{1}\cup A_{2}\cup B$. We set
$s_{i+1}^{\prime}(b)=u$ and we add $b$ to $B$. We repeat until $A_{3}\setminus
B$ is empty.

######  Claim 1.

We always have enough vertices in the sets $U_{S}\setminus\\{s_{0}(a),t(a)\mid
a\in A\\}$ in order to select vertices that have the wanted properties for the
agents in the set $A_{3}$.

Before we prove this claim we need to observe that, for any turn $i\in\ell$
and any agent $a\in A$, $s^{\prime}_{i}(a)\in U_{S}$ if and only if
$s_{i}(a)\in V_{S}$. This is obvious if $a\in A_{1}\cup A_{3}$. To prove this
for the agents in $A_{2}$, consider the first turn $j<i$ such that
$s_{k}(a)=s_{i}(a)$ for all $j\leq k\leq i$. During turn $j$, $a$ belonged to
$A_{1}\cup A_{3}$ (defined during that turn) therefore it is true.

Proof of the claim. Assume that we have an agent $a\in A_{3}$, $s_{i+1}(a)=v$
and $S=N_{G}(v)$. We consider two cases, either $|V_{S}|>3k$ or not. In the
former, we know that $|U_{S}\setminus\\{s_{0}(c),t(c)\mid c\in A\\}|=k$.
Therefore, since $|A\setminus\\{a\\}|=k-1$, even if for all agents $b\in A$ we
have that $s_{i+1}^{\prime}(b)\in U_{S}\setminus\\{s_{0}(c),t(c)\mid c\in
A\\}$, there exists at least one vertex in $U_{S}\setminus\\{s_{0}(c),t(c)\mid
c\in A\\}$ that can be assigned to $s_{i+1}^{\prime}(a)$.

In the latter cases, let $A^{\prime}\subseteq A$ be the set of agents where
$b\in A^{\prime}$ if and only if $s_{i+1}(b)\in V_{S}$ and
$s_{i+1}(b)\notin\\{s_{0}(b),t(b)\mid b\in A\\}$. Since
$s_{i+1}^{\prime}(b)\in U_{S}\setminus\\{s_{0}(b),t(b)\mid b\in A\\}$ only if
$s_{i+1}(b)\in V_{S}$, we need to prove that
$|A^{\prime}|\leq|U_{S}|\setminus\\{s_{0}(b),t(b)\mid b\in A\\}$. This is
indeed the case, as we have assumed that $|V_{S}|\leq 3k$, and therefore
$U_{S}=V_{S}$. $\diamond$

Notice that, for any agent $a\in A$, either $s_{i}^{\prime}(a)=s_{i}(a)$ or
$s_{i}^{\prime}(a)$ is a twin of $s_{i}(a)$. The same holds for
$s_{i+1}^{\prime}(a)$ and $s_{i+1}(a)$. We will show that
$s_{i+1}^{\prime}(a)$ is either equal to $s_{i}^{\prime}(a)$ or its neighbor.
Consider the case where $s_{i}(a)=s_{i+1}(a)$. Regardless of whether $a\in
A_{1}$ or $a\in A_{2}$, we have that $s_{i}^{\prime}(a)=s_{i+1}^{\prime}(a)$
which is a valid move. Now, consider the case where $s_{i}(a)\neq s_{i+1}(a)$.
In this case, we know that $s_{i}(a)$ and $s_{i+1}(a)$ are neighbors in $G$.
Since $s_{i}^{\prime}(a)=s_{i}(a)$ or $s_{i}^{\prime}(a)$ is a twin of
$s_{i}(a)$ and the same holds for $s_{i+1}^{\prime}(a)$ and $s_{i+1}(a)$, we
can conclude that $s_{i}^{\prime}(a)$ and $s_{i+1}^{\prime}(a)$ are neighbors
in $G$. Therefore $s_{i}^{\prime}(a)$ and $s_{i+1}^{\prime}(a)$ are neighbors
in $H$ and the move is valid.

Next, we show that there are no two agents that occupy the same vertex during
the same turn. Notice that the the values $s_{i+1}(a)$ for $a\in A_{3}$ are
selected in such a way that no agent of $A_{3}$ will ever occupy the same
vertex as any other agent. Therefore we need to show that the same holds true
for agents in $A_{1}\cup A_{2}$. Assume that this is not true and there exist
two agents $a,b\in A_{1}\cup A_{2}$ such that
$s_{i+1}^{\prime}(a)=s_{i+1}^{\prime}(b)$. We consider three cases.

Case 1. $\boldsymbol{{a,b}\subseteq A_{1}}$: Since $s_{1},\ldots,s_{\ell}$ is
a feasible solution, we have that $s_{i+1}(a)\neq s_{i+1}(b)$. Furthermore,
since ${a,b}\subseteq A_{1}$, we have that $s_{i+1}^{\prime}(a)=s_{i+1}(a)\neq
s_{i+1}(b)=s_{i+1}^{\prime}(b)$. This is a contradiction.

Case 2. $\boldsymbol{a\in A_{1}$and$b\in A_{2}}$: Since
$s_{1},\ldots,s_{\ell}$ is feasible, we have that $s_{i}(a)\neq s_{i}(b)$ and
$s_{i+1}(a)\neq s_{i+1}(b)$.

We also have that $s_{1}^{\prime},\ldots,s_{i}^{\prime}$ is feasible and,
thus, $s_{i}^{\prime}(a)\neq s_{i}^{\prime}(b)$. Since $a\in A_{1}$, we have
that $s_{i+1}^{\prime}(a)=s_{i+1}(a)\in U\cup\\{s_{0}(c),t(c)\mid c\in A\\}$.
Furthermore, we have assumed that $s_{i+1}^{\prime}(a)=s_{i+1}^{\prime}(b)$
and $b\in A_{2}$. It follows that $s_{i}^{\prime}(b)=s_{i+1}^{\prime}(b)\in
U\cup\\{s_{0}(c),t(c)\mid c\in A\\}$. By the hypothesis for $s_{i}^{\prime}$
and $s_{i}^{\prime}(b)\in U\cup\\{s_{0}(c),t(c)\mid c\in A\\}$ we have that
$s_{i}^{\prime}(b)=s_{i}(b)$. Therefore,
$s_{i+1}(b)=s_{i}(b)=s_{i}^{\prime}(b)=s_{i+1}^{\prime}(b)=s_{i+1}^{\prime}(a)=s_{i+1}(a)$.
This is a contradiction as $s_{i+1}(a)\neq s_{i+1}(b)$.

Case 3. $\boldsymbol{{a,b}\subseteq A_{2}}$: Since $a\in A_{2}$, we have that
$s_{i}^{\prime}(a)=s_{i+1}^{\prime}(a)$. Also, since $a\in A_{2}$, we have
that $s_{i}^{\prime}(b)=s_{i+1}^{\prime}(b)$. By the induction hypothesis, we
know that $s_{i}^{\prime}(a)\neq s_{i}^{\prime}(b)$, from which follows that
$s_{i+1}^{\prime}(a)\neq s_{i+1}^{\prime}(b)$. This is a contradiction.

Therefore, no two agents occupy the same vertex during the same turn. Also,
notice that the wanted properties between $s_{i+1}$ and $s_{i+1}^{\prime}$
hold by the construction. Finally, since $s_{\ell}=t$, we conclude that
$s^{\prime}_{\ell}=t$.

This shows that any feasible solution of $\langle G,A,s_{0},t,\ell\rangle$ can
be transformed into a feasible solution of $\langle H,A,s_{0},t,\ell\rangle$.
Therefore, $\langle H,A,s_{0},t,\ell\rangle$ is a kernel of the claimed size.
∎

###  3.4 Bounded number of agents plus diameter

######  Theorem 14.

The MAPF problem can be solved by an FPT-algorithm parameterised by the
diameter $d$ of $G$ plus the number of agents $k$ in $2^{O(k^{2}\cdot
d\cdot\log d)}\cdot m\cdot\log n$ time.

The result is a consequence of the fact that in any sufficiently large graph
$G$, there is always a feasible swap-free solution with makespan at most
$O(d\cdot k)$.

######  Lemma 2.

Let $\langle G,A,s_{0},t,\ell\rangle$ be an instance of MAPF such that for
every $a\in A$, the vertex $t(a)$ is reachable from $s_{0}(a)$ and $G$ has at
least $(5\cdot d\cdot k)^{d+1}$ vertices where $d$ is the diameter of $G$ and
$k$ is the number of agents. There exists a swap-free feasible solution of
makespan $O(d\cdot k)$.

###### Proof.

Let us assume that $G$ is connected as otherwise, the claim follows by
considering each connected component separately. Any graph with maximum degree
$\Delta>2$ and diameter $d$ has its number of vertices bounded by the Moore
bound $1+\Delta\frac{(\Delta-1)^{d}-1}{\Delta-2}$, see [14]. Therefore, there
is a vertex $v$ of degree at least $5\cdot d\cdot k$ in $G$.

Without loss of generality, let $A=[k]$ be the set of agents. For each agent
$i\in A$, let $P_{i}$ be an arbitrary shortest path between $s_{0}(i)$ and
$t(i)$ and let $H$ be the subgraph of $G$ obtained as the union
$\bigcup_{i\in[k]}P_{i}$. First, observe that $H$ contains at most
$k\cdot(d+1)$ vertices since each $P_{i}$ is a shortest path in $G$. If $H$ is
disconnected, it consists of at most $k$ connected components and we keep
connecting disconnected components using shortest paths until we make it
connected. Thereby, we obtain a connected graph on at most $2\cdot
k\cdot(d+1)$ vertices including the starting and target vertices of all
agents.

Next, we construct a graph $H^{\prime}$ from $H$ in the following way. If $H$
does not contain the high-degree vertex $v$, we connect it by adding an
arbitrary shortest path between $v$ and $H$. In doing so, we increase the
number of vertices by at most $d-1$. Moreover, we add to $H^{\prime}$
arbitrary $k$ neighbors $w_{1},\dots,w_{k}$ of $v$ that are contained neither
in $H$ nor in the added shortest path between $H$ and $v$. This is possible
since there are at most $2\cdot k\cdot(d+1)+d-1\leq 4\cdot d\cdot k$ such
vertices and $v$ has at least $5\cdot d\cdot k$ neighbors. In total,
$H^{\prime}$ contains at most $O(d\cdot k)$ vertices.

Let $T$ be an arbitrary spanning tree of $H^{\prime}$ and let
$i_{1},\dots,i_{k}$ be an ordering of the set of agents $[k]$ such that
$\operatorname{dist}_{T}(s_{0}(i_{j}),v)\leq\operatorname{dist}_{T}(s_{0}(i_{j+1}),v)$
for every $j\in[k-1]$ where $\operatorname{dist}_{T}(x,y)$ is the distance
between $x$ and $y$ in $T$. In other words, we order agents in increasing
order with respect to the distance between their starting positions and $v$ in
$T$.

We construct a feasible solution with short makespan in the following way. We
choose to describe the movements of all agents instead of tediously defining
all the functions $s_{1},s_{2},\ldots$. For $j\in[k]$, the agent $i_{j}$
starts moving at time $j$ and follows the shortest path from $s_{0}(i_{j})$ to
$w_{i_{j}}$ in $T$ without any further delay. We claim that there cannot be
any conflicts. Assume for a contradiction that there exist
$j,j^{\prime}\in[k]$ such that the agents $i_{j}$ and $i_{j^{\prime}}$ collide
at time $p$. Let us assume that $j<j^{\prime}$. Observe that such a collision
must occur only once the agents start moving and before they reach the vertex
$v$ because of the ordering by distances from $v$. In particular the agent
$i_{j}$ is at time $p$ in distance
$\operatorname{dist}_{T}(s_{0}(i_{j}),v)-p+j-1$ from vertex $v$ and the agent
$i_{j^{\prime}}$ is at distance
$\operatorname{dist}_{T}(s_{0}(i_{j^{\prime}}),v)-p+j^{\prime}-1$. However, we
have
$\operatorname{dist}_{T}(s_{0}(i_{j}),v)\leq\operatorname{dist}_{T}(s_{0}(i_{j^{\prime}}),v)$
due to the way we defined the ordering and $j<j^{\prime}$ by assumption.
Therefore, the distance of the agent $i_{j}$ is strictly smaller than that of
agent $i_{j^{\prime}}$ and we reach contradiction.

Once we stashed every agent $i\in[k]$ in the leaf $w_{i}$, we use the same
strategy in reverse with respect to their target positions. In the first half
of the process, it takes $k$ turns before all the agents start moving and
afterwards, they must all arrive at the leaves $w_{1},\dots,w_{k}$ in at most
$O(d\cdot k)$ turns since that is the total number of vertices in $T$. The
same bound holds for moving the agents from $w_{1},\dots,w_{k}$ to their
target positions and thus, the total makespan of this solution is $O(d\cdot
k)$. ∎

###### Proof of Theorem 14.

Let $n$ denote the number of vertices of $G$. If $n<(5\cdot d\cdot k)^{d+1}$,
we simply search the $k$-agent search space of size $(d\cdot k)^{O(kd)}$ using
any of the standard graph searching algorithms (BFS, A*, etc.). Otherwise, we
distinguish two cases. Either $\ell<C\cdot d\cdot k$ where the constant $C$ is
given by Lemma 2, and we invoke the FPT-algorithm of Theorem 6 on the given
instance. Otherwise, we invoke the same FPT-algorithm on a modified instance
with $\ell=C\cdot d\cdot k$ which is guaranteed to be equivalent by Lemma 2. ∎

######  Corollary 1.

Let $\mathcal{G}$ be a class of bounded treedepth, modularwidth, shrubdepth,
or MIM-width. The MAPF problem is in FPT parameterised by the number of agents
$k$ if $G\in\mathcal{G}$.

###### Proof.

In each case, the diameter of $G$ is bounded by some function of the
respective parameter and thus, the result follows directly from Theorem 14. In
fact, we show that in each case the respective parameter implies non-existence
of long (induced) paths. A graph with treedepth $w$ cannot contain path of
length $2^{w}$ even as a subgraph, see [22]. Any graph class with bounded
shrubdepth cannot contain arbitrarily long induced paths, see [10].
Modularwidth is monotone under taking induced subgraphs, and a path of $n$
vertices has modularwidth $n$. Therefore, a graph with modularwidth $k$ cannot
contain an induced path of length $k$. Finally, the MIM-width of a graph $G$
is defined as the size of the largest induced matching in $G$. Thus clearly,
there cannot be an induced path of length more than $2w+1$ in any graph with
MIM-width $w$. ∎

##  4 Hardness

###  4.1 Number of agents

Allow us to first remind the following notation. In a tree $T$ rooted at $r$,
the $depth(v)$ is the number of edges in a shortest path from $v$ to $r$. The
$height(T)$ is $\max_{v\in V(T)}depth(v)+1$.

See 1

$s^{\prime}_{1}$$s^{\prime}_{2}$$t^{\prime}_{1}$$t^{\prime}_{2}$

(a) A topological ordering of a directed acyclic graph $D$.

$s_{2}$$s_{1}$$t_{1}$$t_{2}$

(b) The graph $G$ constructed based on $D$.

Figure 2: An example for the construction used in the proof of Theorem 1. The
color white denotes the original vertices, while the auxiliary vertices are
colored black. The colors red and blue denote the two vertex-disjoint paths of
$D$ in subfigure (a), and the corresponding trajectories of $G$ that the two
agents will follow in subfigure (b). Vertices lying on the same vertical line
in (b) belong in the same (sub-)layer.

###### Proof.

The reduction is from the $k$-disjoint shortest paths problem, which was shown
to be $\W[1]$-hard parameterised by $k$ in [18], even when the graph given in
the input is directed and acyclic. The input of this problem consists of a
graph $G$ and a set of pairs of vertices
$\mathcal{P}=\\{(s_{i},t_{i}):i\in[k]\\}$; the question is whether there
exists a set of $(s_{i},t_{i})$-paths hat are of minimum length and pairwise
vertex-disjoint.

Let $\langle D,\mathcal{P}^{\prime}\rangle$ be an instance of the $k$-disjoint
shortest paths problem, where $D$ is a directed acyclic graph. Let
$v_{1},\dots,v_{n}$ be a topological ordering of the vertices of $D$. We
define _layers_ $l_{0},\dots,l_{n+1}$ such that $v_{i}\in l_{i}$ for all
$i\in[n]$ while $l_{0}$ and $l_{n+1}$ are initially empty. We begin
constructing the graph for our reduction, illustrated in Figure 2. We start
with $G$ being the underlying (undirected) graph of $D$. Let us say that the
vertices of $G$ at this stage are the _original vertices_. Let $A=\\{a_{i}\mid
i\in[k]\\}$ denote the set of agents. For each $i\in[k]$, add the vertices
$s_{0}(a_{i})$ and $t(a_{i})$ in layers $l_{0}$ and $l_{n+1}$ respectively, as
well as the edges $s_{0}(a_{i})s^{\prime}_{i}$ and $t(a_{i})t^{\prime}_{i}$.
Observe that the vertices we added to the layers $l_{0}$ and $l_{n+1}$ are all
of degree $1$. Currently, $G$ contains a unique vertex in $l_{0}$ for each
$s^{\prime}_{i}$, and a unique vertex in layer $l_{n+1}$ for each
$t^{\prime}_{i}$, $i\in[k]$, and is of maximum degree $\Delta\leq n$. In what
follows, we modify $G$ so that $\Delta(G)\leq 3$ and all the shortest
$(s_{0}(a_{i}),t(a_{i}))$-paths are of the same length.

We now modify $G$ so that $\Delta(G)\leq 3$ as follows. Let $v_{i}$,
$i\in[n]$, be the first vertex such that $d_{G}(v_{i})\geq 4$. First, add to
$G$ the trees $T_{i}^{1}$ and $T_{i}^{2}$, both being a copy of the complete
binary tree of height $H=\lceil\log(\Delta(D)+1)\rceil+1$. Let $r_{i}^{1}$ and
$r_{i}^{2}$ denote the roots of $T_{i}^{1}$ and $T_{i}^{2}$ respectively.
Then, add the edges $v_{i}r_{i}^{1}$ and $v_{i}r_{i}^{2}$. We insert the
vertices of the newly added trees in new _sub-layers_ of $l_{i}$ defined as
follows. For each vertex $u$ that belongs to $T_{i}^{1}$ ($T_{i}^{2}$ resp.)
and $u$ is at depth $0\leq h\leq H-1$, add $u$ inside the layer $l_{i,h}^{1}$
($l_{i,h}^{2}$ resp.). Then, for each vertex $v$ that belongs in a layer
$l_{j}$ or a sub-layer $l_{j,H}^{2}$, for $j<i$ (or a sub-layer $l_{j,H}^{1}$
for $j>i$ resp.), such that $vv_{i}\in E(G)$, delete the edge $vv_{i}$ and add
an edge between $v$ and any one of the vertices of $T_{i}^{1}$ ($T_{i}^{2}$
resp.) that is still of degree $1$ (whose existence is guaranteed by the
height of the the binary trees we used). Repeat this process as long as there
exist vertices in $G$ that are of degree greater than $3$. This terminates
after at most $n$ repetitions, and adds in total at most $\mathcal{O}(n^{2})$
vertices to $G$. The resulting graph $G$ has maximum degree at most $3$.

Lastly, we modify $G$ so that all the shortest $(s_{0}(a_{i}),t(a_{i}))$-paths
are of the same length. To do so, we will make use of the layers and sub-
layers defined thus far. Let $uv\in E(G)$ and $i,j$ be such that $u$ and $v$
belong in layers $l$ and $l^{\prime}$, respectively, with
$l\in\\{l_{i},l_{i,H}^{1},l_{i,H}^{2}\\}$ and
$l^{\prime}\in\\{l_{j},l_{j,H}^{1},l_{j,H}^{2}\\}$ and $|i-j|>1$; such edges
are called _bad_. We subdivide each bad edge $e\in E(G)$ so that each layer
and sub-layer between $l$ and $l^{\prime}$ receives a new vertex. Observe that
in the resulting graph, all the shortest $(s_{0}(a_{i}),t(a_{i}))$-paths have
the same length $L$ Finally, all the vertices of $G$ at this stage that are
not original, are denoted as _auxiliary_. This finishes the construction of
$G$.

We are now ready to proceed with our reduction. In particular, we will show
that $\ell(\langle G,A,s_{0},t\rangle)\leq L$ if and only if $\langle
D,\mathcal{P}^{\prime}\rangle$ is a yes-instance of the $k$-disjoint shortest
paths problem.

Let us first assume that $\langle D,\mathcal{P}^{\prime}\rangle$ is a yes-
instance of the $k$-disjoint shortest paths problem and let
$\\{P^{\prime}_{i}=(s_{i}^{\prime}=u_{1}^{i},\dots,u_{p}^{i}=t_{i}^{\prime}):i\in[k],p\leq
n\\}$ be a set of disjoint shortest $(s_{i}^{\prime},t_{i}^{\prime})$-paths in
$D$. For each $i\in[k]$ we define an $(s_{0}(a_{i}),t(a_{i})$ path $P_{i}$ as
follows. The first and last vertices of $P_{i}$ are $s_{0}(a_{i})$ and
$t(a_{i})$ respectively. Then, starting from $s_{0}(a_{i})$, we follow the
edges of $G$ until we reach an original vertex $v$. From the construction of
$G$, it follows that $v=s_{i}^{\prime}$. We proceed by following the original
vertices of $G$ according to $P^{\prime}_{i}$ as long as possible. Let us
assume that it is not possible to do so, and let $u$ be the last (original)
vertex we have inserted into $P_{i}$ and $v$ be the next vertex proposed by
$P^{\prime}_{i}$.

######  Claim 2.

If $(uv)\in A(D)$ and $uv\notin E(G)$, there exists a unique $(u,v)$-path $P$
in $G$.

Proof of the claim. Let $u\in l_{i}$ and $v\in l_{j}$. If $d_{D}(u)\leq
d_{D}(v)\leq 3$, then it follows that during the construction of $G$, the edge
$uv$ was a bad edge that got subdivided into a path, which is exactly $P$.
Otherwise, at least one of $T_{i}^{2}$ and $T_{j}^{1}$ exists in $G$. We
distinguish cases:

    * –

if both $T_{i}^{2}$ and $T_{j}^{1}$ exist, then by the construction of $G$ we
have that there exist unique vertices $w\in l_{i,H}^{2}$ and $z\in
l_{j,H}^{1}$ such that $wz\in E(G)$ or there exists a unique $(w,z)$-path (the
result of the subdivision of a bad edge). Follow the unique path leading from
$u$ to $w$, continue to $z$, and then follow the unique path leading from $w$
to $v$;

    * –

if only $T_{i}^{2}$ exists, then by the construction of $G$ we have that there
exists a unique vertex $w\in l_{i,H}^{2}$ such that $wv\in E(G)$ or there
exists a unique $(w,v)$-path (the result of the subdivision of a bad edge).
Follow the unique path leading from $u$ to $w$ and then continue to $v$;

    * –

if only $T_{j}^{1}$ exists, then by the construction of $G$ we have that there
exists a unique vertex $z\in l_{j,H}^{1}$ such that $uz\in E(G)$ or there
exists a unique $(u,z)$-path (the result of the subdivision of a bad edge).
Start by moving from $u$ to $z$ and then follow the unique path leading from
$z$ to $v$.

$\diamond$

So, following the unique path as it is defined in the above claim, we are able
to reach $v$. From there, we continue following $P^{\prime}_{i}$ as long as
possible. This finishes the definition of $P_{i}$. Observe that, for each
$i\in[k]$, we have that $P_{i}$ is of length exactly $L$, as it contains
exactly one vertex of each layer and sub-layer of $G$. Also, observe that by
their construction, the paths $P_{1},\dots,P_{k}$ are pairwise vertex-disjoint
paths. This means that any two agents $a_{i}$ and $a_{j}$ that, at each turn,
move from their current vertex to the next one according to $P_{i}$ and
$P_{j}$ respectively, are never going to attempt to go on the same vertex, and
they are going to reach their destinations after $L$ turns. Thus,
$\ell(\langle G,A,s_{0},t\rangle)\leq L$.

For the reverse direction, assume that $\ell(\langle G,A,s_{0},t\rangle)=L$
and let $s_{i}$, $i\in[L]$, be the sequence of functions such that
$s_{i}:A\rightarrow V(G)$ gives us the set of vertices on which the agents are
placed at the end of the $i^{th}$ turn. For each $j\in[k]$, let the path
$P^{\prime}_{j}$ be defined as follows. Consider the turns $i_{1},\dots,i_{p}$
(for $p\leq L$) such that the agent $a_{j}$ is visiting an original vertex of
$G$ according to $s_{i_{m}}$, $m\in[p]$. Let
$P^{\prime}_{j}=(s_{i_{1}}(a_{j}),\dots,s_{i_{p}}(a_{j}))$. It follows from
the construction of $G$ that $P^{\prime}_{j}$ is indeed a path of $D$and that
$s_{i_{1}}(a_{j})=s_{j}^{\prime}$ and $s_{i_{p}}(a_{j})=t_{j}^{\prime}$. Also,
since all the $(s_{0}(a_{i}),t(a_{i}))$-paths of $G$ are of length $L$, we
have that at each turn, all the agents are located on vertices of the same
layer or sub-layer of $G$. Moreover, by the construction of $G$, each layer
contains at most one original vertex. It follows that $P^{\prime}_{j}$
contains at most one vertex for each layer of $D$ and, thus, that
$P^{\prime}_{j}$ is a shortest $(s_{j}^{\prime},t_{j}^{\prime})$-path. It
remains to show that these paths that we defined are also pairwise vertex-
disjoint. Towards a contradiction, assume that there are $j_{1},j_{2}\in[k]$
such that the paths $P^{\prime}_{j_{1}}$ and $P^{\prime}_{j_{2}}$ intersect on
a vertex $v$. Then, by the definition of these paths, we have that there
exists a turn $i$ such that $s_{i}(a_{j_{1}})=s_{i}(a_{j_{2}})=v$, which
contradicts the feasibility of the solution of the Multiagent Pathfinding
Problem. ∎

###  4.2 Trees of bounded maximum degree

See 5

###### Proof.

It was recently shown that the Parallel Token Swapping is NP-hard on trees
[1]. This problem is exactly the same as the Multiagent Pathfinding Problem
when swaps are allowed and the number of agents is equal to the number of
vertices of the tree. Here, we present a reduction from this version of the
problem to the version where swaps are not allowed, the input graph is a tree
with maximum degree $5$, and the number of agents is arbitrary. Let $\langle
T^{\prime},A^{\prime},s_{0}^{\prime},t^{\prime}\rangle$ be an instance of
Multiagent Pathfinding Problem, where swaps are allowed and $T^{\prime}$ is a
tree. We will construct an instance $\langle T,A,s_{0},t\rangle$ of the
Multiagent Pathfinding Problem where swaps are not allowed and $T$ is a tree
of maximum degree $5$, such that $\ell(\langle
T^{\prime},A^{\prime},s_{0}^{\prime},t^{\prime}\rangle)\leq\ell^{\prime}$ if
and only if $\ell(\langle T,A,s_{0},t\rangle)\leq\ell$, for a given value
$\ell^{\prime}$.

First we present the construction of $T=(V,E)$. Start with
$T^{\prime}=(V^{\prime},E^{\prime})$ and let $h$ be the value
$\\{\lceil\log\Delta(T^{\prime})\rceil+1\\}$ if this is even, otherwise,
$h=\\{\lceil\log\Delta(T^{\prime})\rceil+2\\}$. We will bound the degree of
this graph by replacing the edges between any non-leaf vertex and its children
with a complete binary tree of height $h$. In particular, for each non-leaf
vertex $v\in V^{\prime}$, we create $T_{v}$, a complete binary tree of height
$h$ rooted by a vertex $r_{v}$. Let $U$ be the set $\bigcup_{v\in
V^{\prime}}V(T_{v})$ and $E^{\prime}=\bigcup_{v\in V^{\prime}}E(T_{v})$. We
also add to $E^{\prime}$ the set of edges $\\{vr_{v}:v\in V^{\prime}\\}$. Now
we will replace the edges of the original graph. For each non-leaf vertex
$v\in V^{\prime}$ let $v_{i}$, $i\in[d_{T^{\prime}}(v)]$, be the children of
$v$ in $T^{\prime}$ and $l_{i}$, $i\in[d_{T^{\prime}}(v)]$, be
$d_{T^{\prime}}(v)$ distinguished leaves in $T_{v}$. We remove
$\\{vv_{i}:i\in[d_{T^{\prime}}(v)]\\}$ from $E^{\prime}$ and we add
$\\{v_{i}l_{i}:i\in[d_{T^{\prime}}(v)]\\}$ to $E^{\prime}$. Notice that the
resulting graph is a tree of maximum degree $3$.

To complete the construction, for each vertex $u\in U$, we add two paths
$P^{u,s}=(u_{s,0},\ldots u_{s,\ell^{\prime}m-1})$ and $P^{u,t}=(u_{t,1},\ldots
u_{t,(\ell^{\prime}-1)m})$, where $m=2+h$, and the edges
$uu_{s,\ell^{\prime}m-1}$ and $uu_{t,1}$. Let $W$ be the set of all the
vertices in these paths and $E_{W}$ all the edges with at least one incident
vertex belonging in $W$. The final graph is $T=(V^{\prime}\cup U\cup
W,E^{\prime}\cup E_{W})$. Notice that the addition of $E_{W}$ increases the
maximum degree of $T$ to at most $5$.

Next, we define the set of agents $A$ and the functions $s_{0}$ and $t$. We
start by setting $A=A^{\prime}$; we will call these the original agents. Also
for each vertex $u\in U$ we will add $\ell^{\prime}$ path agents $a_{{u,i}}$,
$i\in[\ell^{\prime}]$ to $A$. We define the function $s_{0}$ as follows. For
any original agent $a$, $s_{0}(a)=s_{0}^{\prime}(a)$. For each path agent
$a_{{u,i}}$, where $u\in U$ and $i\in[\ell^{\prime}]$,
$s_{0}(a_{{u,i}})=u_{s,(i-1)m}$. Finally, we define the function $t$ as
follows. For any original agent $a$, $t(a)=t^{\prime}(a)$. For each path agent
$a_{{u,i}}$, where $u\in U$ and $i\in[\ell^{\prime}]$, if $i>1$ then
$t(a_{{u,i}})=u_{t,(i-1)m}$ and $t(a_{{u,1}})=u$.

######  Claim 3.

If $\ell(\langle
T^{\prime},A^{\prime},s_{0}^{\prime},t^{\prime}\rangle)\leq\ell^{\prime}$ then
$\ell(\langle T,A,s_{0},t\rangle)\leq\ell=\ell^{\prime}m$.

Proof of the claim.

Let $s_{0}^{\prime},s_{1}^{\prime},\ldots,s_{\ell^{\prime}}^{\prime}$ be a
feasible solution of $\langle
T^{\prime},A^{\prime},s_{0}^{\prime},t^{\prime}\rangle$. We will define a new
sequence $s_{0},s_{1},\ldots,s_{\ell}$ that is a feasible solution of $\langle
T,A,s_{0},t\rangle$. To do so, for each $s_{i}^{\prime}$,
$i\in[\ell^{\prime}]$, we create a sequence $s_{(i-1)m+1},\ldots,s_{im}$. The
definition is inductive. First, $s_{0}$ is the starting position of each agent
in $\langle T,A,s_{0},t\rangle$. Assuming that we have defined the sequence
until the $s_{(i-1)m}$, we define the $s_{(i-1)m+1},\ldots,s_{im}$ as follows:

    * –

for each agent $a_{u,p}$, $u\in U$ and $p\in[\ell^{\prime}]$, for $j=1$ to
$m$:

      * *

if $s_{(i-1)m+j-1}(a_{u,p})=u$ then $s_{(i-1)m+j}(a_{u,p})=u_{t,1}$;

      * *

if $s_{(i-1)m+j-1}(a_{u,p})=u_{s,\ell^{\prime}m-1}$ then
$s_{(i-1)m+j}(a_{u,p})=u$;

      * *

if $s_{(i-1)m+j-1}(a_{u,p})=u_{s,q}$ for some
$q\in\\{0\\}\cup[\ell^{\prime}m-2]$, then $s_{(i-1)m+j}(a_{u,p})=u_{s,q+1}$;

      * *

if $s_{(i-1)m+j-1}(a_{u,p})=u_{t,q}$ for some $q\in[(i-1)m-1]$, then
$s_{(i-1)m+j}(a_{u,p})=u_{t,q+1}$.

Now, we need to deal with the original agents. Notice that, since $T^{\prime}$
is acyclic, for any agent $a$ and turn $i\in[\ell^{\prime}]$, we either have
that $s_{i-1}^{\prime}(a)=s_{i}^{\prime}(a)$ or there exists an agent $b$ such
that $s_{i-1}^{\prime}(a)=s_{i}^{\prime}(b)$ and
$s_{i-1}^{\prime}(b)=s_{i}^{\prime}(a)$ ($a$ and $b$ swap positions).

    * –

for each original agent $a$, such that
$s_{i-1}^{\prime}(a)=s_{i}^{\prime}(a)$:

      * *

we create the sequence $s_{(i-1)m+1}(a)=\ldots=s_{im}(a)=s_{i}^{\prime}(a)$.

    * –

for each pair of original agents $(a,b)$, such that
$s_{i-1}^{\prime}(a)=s_{i}^{\prime}(b)$ and
$s_{i-1}^{\prime}(b)=s_{i}^{\prime}(a)$:

      * *

W.l.o.g., assume that $s_{i-1}^{\prime}(a)$ is the parent of
$s_{i}^{\prime}(a)$ in $T^{\prime}$. Let
$(s_{i-1}^{\prime}(a)=v_{0},v_{1},\ldots,v_{h},v_{h+1}=s_{i}^{\prime}(a))$ be
the unique path between $s_{i-1}^{\prime}(a)$ and $s_{i}^{\prime}(a)$ in $T$
and $v^{\prime}_{\nicefrac{{h}}{{2}}+1}$ be the child of
$v_{\nicefrac{{h}}{{2}}}$ that does not belong in that path.

      * *

For $b$ we set $s_{im-1}(b)=s_{im}(b)=s^{\prime}_{i}(b)$ and
$s_{(i-1)m+j}(b)=v_{h-j+1}$ for all $j\in[h]$.

      * *

For $a$ we set $s_{(i-1)m+j}(a)=v_{j}$ for all $j\in[\nicefrac{{h}}{{2}}]$,
$s_{(i-1)m+\nicefrac{{h}}{{2}}+1}(a)=v^{\prime}_{\nicefrac{{h}}{{2}}+1}$ and
$s_{(i-1)m+j}(a)=v_{j-1}$ for all $j\in[h+2]\setminus[\nicefrac{{h}}{{2}}+1]$.

Notice that the previous sequence is feasible as the agents always move form
one vertex to one of its neighbors and no two agents occupy the same vertex at
the end of the same turn. $\diamond$

It remains to show that if $\ell(\langle T,A,s_{0},t\rangle)\leq\ell$ then,
$\ell(\langle
T^{\prime},A^{\prime},s_{0}^{\prime},t^{\prime}\rangle)\leq\ell^{\prime}$.
Assume that $\ell(\langle T,A,s_{0},t\rangle)=\ell$ and let
$s_{1},\ldots,s_{\ell}$ be a feasible solution. First we show that, in any
such solution, the movements of path agents are known.

######  Claim 4.

In any solution of $\langle T,A,s_{0},t\rangle$ that has makespan
$\ell=m\ell^{\prime}$, any path agent $a$ needs to constantly move through the
shortest path between its starting and finishing positions. Also, any vertex
$u\in U$ is occupied by the agent $a_{u,i}$ during the turn $im$.

Proof of the claim. Let $a_{u,i}$, for some $u\in U$ and $i\in\ell^{\prime}$,
be a path agent. The unique path between $s_{u,i}$ and $t_{u,i}$ is
$(u_{s,im-1},\ldots u_{s,\ell m-1},u,u_{t,1},\ldots,u_{t,im})$. This path is
of length $m\ell^{\prime}$ (number of edges) therefore $a_{u,i}$ needs to
constantly move through this path in order for a sequence with makespan
$\ell=m\ell^{\prime}$ to be valid. For the second part of the claim, it
suffices to observe that $u$ belongs in the path that $a_{u,i}$ needs to move
through, and $s_{u,i}=u_{s,im-1}$ has distance exactly $im$ from $u$.
$\diamond$

Now, we show that the original agents occupy vertices of $V^{\prime}$ during
specific turns.

######  Claim 5.

For any original agent $a$ it holds that:

    * –

for all $i\in[\ell^{\prime}]\cup\\{0\\}$, $s_{im}(a)\in V^{\prime}$ and

    * –

for all $i\in[\ell^{\prime}]$, $s_{im}(a)$ is a neighbor of $s_{(i-1)m}(a)$ in
$T^{\prime}$.

Proof of the claim. Due to Claim 4, we know that $s_{im}(a)\notin U$. We need
to prove that that $s_{im}(a)\notin W$. Assume that there exists an original
agent $a$ such that $s_{im}(a)=v\in W$ for an $i\in\ell^{\prime}$. We consider
two cases: either $v=u_{t,q}$ for some $u\in U$ and $q\in[(\ell^{\prime}-1)m]$
or $v=u_{s,q}$ for some $u\in U$ and $q\in[\ell^{\prime}m-1]$.

Case 1. $\boldsymbol{(v=u_{t,q})}$: Notice that there exists a path agent $b$
such that $s_{im}(b)=u$ and, in any solution of makespan $\ell$, they need to
continue moving through the path $P^{u,t}$. Since swaps are not allowed, the
agent $a$ cannot leave the path $P^{u,t}$. Therefore this sequence cannot be a
feasible solution as $t(a)\in V$ by construction.

Case 2. $\boldsymbol{(v=u_{s,q})}$: We show that this is impossible to happen.
Let $i$ be the minimum integer such that $s_{im}(a)=u_{t,q}$. For the path
agent $b=a_{u,\ell^{\prime}-i}$, by the Claim 4 and the fact that
$s_{0}(b)=u_{s,(\ell^{\prime}-i)m-1}$, we know that
$s_{(i-1)m+j-1}(b)=u_{s,(\ell^{\prime}-1)m+j-1}$ for all $j\in[m]$. Finally,
since $i$ is the minimum integer such that $s_{im}(a)=u_{t,q}$, we know that
$s_{(i-1)m}(a)\notin P^{u,s}$. Therefore, if $s_{im}(a)=u_{t,q}$, then $a$ and
$b$ must swap positions during some turn between $(i-1)m$ and $im$,
contradicting the fact that swaps are not allowed.

Therefore, we have shown that $s_{im}(a)\in V^{\prime}$ for every
$i\in[\ell^{\prime}]\cup\\{0\\}$. It remains to show that $s_{im}(a)$ is a
neighbor of $s_{(i-1)m}(a)$ in $T^{\prime}$. Observe that any two neighboring
vertices in $T^{\prime}$ have distance $m-2$ in $T$ while two non-neighboring
vertices in $T^{\prime}$ have distance at least $2m-4$ in $T$. Observe also
that $h\geq 2$ and, thus, $m\geq 6$. Therefore, if $s_{im}(a)$ is not a
neighbor of $s_{(i-1)m}(a)$ in $T^{\prime}$, we would have that in $T$, the
agent $a$ would have to travel a distance of $2m-4$ which is strictly larger
than the $m$ turns during which he is supposed to do so. $\diamond$

Finally, we claim that the sequence
$s^{\prime}_{0},s^{\prime}_{1},\ldots,s^{\prime}_{\ell^{\prime}}$, where
$s^{\prime}_{i}=s^{\prime}_{im}\mid_{A^{\prime}}$ (the $s^{\prime}_{im}$
restricted to the set of the original agents), is a feasible solution of
$\langle T^{\prime},A^{\prime},s_{0}^{\prime},t^{\prime}\rangle$. First notice
that for any agent $a\in A^{\prime}$, we have that $s^{\prime}_{i}(a)$ is a
neighbor of $s^{\prime}_{i-1}(a)$ (by Claim 5). Since $T^{\prime}$ is a tree,
we know that the sequence is feasible if for any agent $a\in A^{\prime}$ and
$i\in[\ell^{\prime}]$, where $s^{\prime}_{i-1}(a)\neq s^{\prime}_{i}(a)$,
there exists an agent $b\in A^{\prime}$ such that
$s^{\prime}_{i}(a)=s^{\prime}_{i-1}(b)$ and
$s^{\prime}_{i}(b)=s^{\prime}_{i-1}(a)$.

Assume that for an agent $a\in A^{\prime}$ and $i\in[\ell^{\prime}]$ we have
$s^{\prime}_{i-1}(a)\neq s^{\prime}_{i}(a)$. Furthermore, let $b$ be the agent
that occupies the vertex $s^{\prime}_{i}(a)$ at the end of turn $i-1$. We will
show that $s^{\prime}_{i}(b)=s^{\prime}_{i-1}(a)$. Let $V_{1}$ and $V_{2}$ be
the vertex sets of the two connected components of $T^{\prime}-e$, where
$e=s^{\prime}_{i-1}(a)s^{\prime}_{i}(a)$. W.l.o.g., assume that
$s^{\prime}_{i-1}(a)\in V_{1}$ and $s^{\prime}_{i}(a)\in V_{2}$. Let $A_{1}$
and $A_{2}$ be the partition of the agent set $A^{\prime}$ where, for any
$i\in[2]$, $a^{\prime}\in A_{i}$ implies that $s_{i-1}^{\prime}(a^{\prime})\in
V_{i}$. Observe that $N(s^{\prime}_{i-1}(a))\cap V_{2}$ contains only the
vertex $s^{\prime}_{i}(a)$. Therefore, the only agent in $A_{2}$ that can move
to $s^{\prime}_{i-1}(a)$ in turn $i$ is $b$ (as $b$ occupies
$s^{\prime}_{i}(a)$ in turn $i-1$). Finally, since $|A_{2}|=|V_{2}|$, if
$s^{\prime}_{i}(b)\neq s^{\prime}_{i-1}(a)$ then, at turn $i$, we would have
$|A_{2}|+1$ agent occupying $|V_{2}|$, which is a contradiction. Therefore,
the aforementioned sequence is a feasible solution of $\langle
T^{\prime},A^{\prime},s_{0}^{\prime},t\rangle$ with makespan $\ell^{\prime}$.
This completes the proof. ∎

###  4.3 Cliquewidth plus makespan

See 10

$s$$t$

(a) The graph $G$.

$s_{1}$$s_{2}$$t_{1}$$t_{2}$

(b) The graph $G^{\prime\prime}$ constructed based on $G$.

Figure 3: An example for the construction used in the proof of Theorem 10 on a
yes-instance $\langle G,s,t,2,3\rangle$ of BEUP. In subfigure (a), the colors
red and blue distinguish two edge-disjoint paths of length $3$. In subfigure
(b), they denote the corresponding trajectories followed by the two path
agents.

###### Proof.

We reduce from the problem Bounded Edge Undirected $(s,t)$-disjoint Paths
(BEUP) where the input consists of an undirected graph $G$ with two distinct
vertices $s,t$ and two positive integers $k$ and $d$; and the question is
whether there are $k$ edge-disjoint $(s,t)$-paths of length at most $d$ in
$G$. In [12], BEUP was shown to be $\W[1]$-hard when parameterised by the
treewidth of $G$ for every fixed $d\geq 10$.

Let $\langle G,s,t,k,d\rangle$ be an instance of BEUP where $G=(V,E)$. We
first describe the high level idea of the reduction. We subdivide each edge of
$G$ with a new vertex and we enforce that this vertex is blocked in all but at
most one turn. This can be done in a similar fashion to the path agents used
in the proof of Theorem 5. Finally, we add to $G$ many twins of each original
vertex simulating that several agents can occupy a single original vertex at
the same time. Any solution to the instance $\langle G,s,t,k,d\rangle$ then
corresponds to moving agents situated on $k$ twins of $s$ to arbitrary $k$
twins of $t$.

Now, we describe the construction formally. First, we subdivide each edge
$e\in E$ with a new vertex $v_{e}$. Afterwards, we add a path $P_{e}$ on
$4d-3$ vertices $v_{e}^{1},v_{e}^{2},\dots,v_{e}^{4d-3}$ such that its middle
vertex $v_{e}^{2d-1}$ is identified with $v_{e}$ and all other vertices are
disjoint from the rest of the graph. Let $G^{\prime}$ be the obtained graph.
It is easy to see that $\operatorname{tw}(G^{\prime})=\operatorname{tw}(G)$.
And therefore, it follows that $\operatorname{cw}(G^{\prime})=3\cdot
2^{\operatorname{tw}(G^{\prime})-1}\leq 3\cdot 2^{\operatorname{tw}(G)-1}$ by
[4].

We now modify $G^{\prime}$ to a graph $G^{\prime\prime}$ by replacing every
original vertex $v\in V$ of $G$ with an independent set of $k$ twins
$v_{1},\dots,v_{k}$. See Figure 3 for example. The treewidth of
$G^{\prime\prime}$ may no longer be bounded by a function of
$\operatorname{tw}(G)$. However, it is easy to see that
$\operatorname{cw}(G^{\prime\prime})=\operatorname{cw}(G^{\prime})$ and thus,
the cliquewidth of $G^{\prime\prime}$ is at most exponential in the treewidth
of $G$.

It remains to define the set of agents $A$ together with their starting and
ending positions. The set of agents $A$ consists of a set of _path agents_
$A_{0}=\\{a_{i}\mid i\in[k]\\}$ and a set of $2d-2$ _edge agents_
$B_{e}=\\{b_{e}^{i}\mid i\in[2d-2]\\}$ for every edge $e\in E$. We set
$s^{\prime}_{0}(a_{i})=s_{i}$, $t^{\prime}(a_{i})=t_{i}$ for every path agent
$a_{i}\in A_{0}$. In other words, the starting and ending positions of path
agents lie in the independent sets corresponding to the original vertices $s$
and $t$, respectively. For every $e\in E$ and every $i\in[2d-2]$, we set
$s^{\prime}_{0}(b_{e}^{i})=v_{e}^{i}$ and
$t^{\prime}(b_{e}^{i})=v_{e}^{2d+i-1}$. We now show that $\ell(\langle
G^{\prime\prime},A,s^{\prime}_{0},t^{\prime}\rangle)\leq 2d$ if and only if
$\langle G,s,t,k,d\rangle$ is a yes-instance of BEUP.

First, let $\langle G,s,t,k,d\rangle$ be a yes-instance of BEUP and let
$\\{P^{\prime}_{i}=(s=u^{i}_{0},\dots,u^{i}_{d_{i}}=t)\mid i\in[k]\\}$ be a
set of $k$ edge-disjoint $(s,t)$-paths in $G$ such that $d_{i}\leq d$ for
every $i\in[k]$. We first define the movement of the path agents. We let the
agent $a_{i}$ follow the natural subdivision of the path $P^{\prime}_{i}$ in
$G^{\prime\prime}$. Formally for every $i\in[k]$, we set
$s^{\prime}_{2j}(a_{i})=(u^{i}_{j})_{i}$ and
$s^{\prime}_{2j-1}(a_{i})=v_{\\{u^{i}_{j-1},u^{i}_{j}\\}}$ for $j\in[d_{i}]$,
and $s^{\prime}_{2j-1}(a_{i})=s^{\prime}_{2j}(a_{i})=t_{i}$ for
$j\in[d_{i}+1,d]$. All the movements of path agents are feasible since in even
turns they occupy pairwise different copies of the original vertices from $G$
and in odd turns, they occupy vertices corresponding to edges on the edge-
disjoint paths $P^{\prime}_{1},\dots,P^{\prime}_{k}$.

It remains to define the movement of the edge agents. Fix an edge $e\in E$ of
$G$. Notice that the vertex $v_{e}$ is used by a path agent in at most one
turn. If that is the case, let $c_{e}$ be the time when the vertex $v_{e}$ is
occupied by a path agent and otherwise, let $c_{e}=2d$. We define the movement
of agents of $B_{e}$ in such a way that they make way for the path agent
exactly at time $c_{e}$. For every $i\in[2d-c_{e}:2d]$, we let the agent
$b_{e}^{i}$ walk directly to its destination using the shortest path of length
$2d-1$. In other words, we set $s^{\prime}_{j}(b_{e}^{i})=v_{e}^{j+i}$ for
$j\in[2d-1]$ and
$s^{\prime}_{2d}(b_{e}^{i})=v_{e}^{2d+i-1}=t^{\prime}(b_{e}^{i})$. Every other
agent from $B_{e}$ moves towards its destination for the first $c_{e}-1$
turns, then waits one turn and continues afterwards with no further delay.
Formally, we set for every $i\in[2d-c_{e}-1]$ and $j\in[2d]$

$s^{\prime}_{j}(b_{e}^{i})=\begin{cases}v_{e}^{j+i}&\text{if $j\leq c_{e}-1$,
and}\\\ v_{e}^{j+i-1}&\text{if $j\geq c_{e}$.}\end{cases}$

It is easy to check that the edge agents in $B_{e}$ are occupying pairwise
different positions at each turn and moreover, they do not swap.

######  Claim 6.

The vertex $v_{e}$ is at time $c_{e}$ not occupied by any agent of $B_{e}$.

Proof of the claim. Assume that there is an agent $b_{e}^{i}$ such that
$s^{\prime}_{c_{e}}(b_{e}^{i})=v_{e}=v_{e}^{2d-1}$. If $i\geq 2d-c_{e}$, then
agent $b_{e}^{i}$ moves without any delays and
$s^{\prime}_{c_{e}}(b_{e}^{i})=v_{e}^{i+c_{e}}\neq v_{e}^{2d-1}$ since
$i+c_{e}\geq 2d$. On the other hand, if $i<2d-c_{e}$ then
$s^{\prime}_{c_{e}}(b_{e}^{i})=v_{e}^{c_{e}+i-1}\neq v_{e}^{2d-1}$ since
$c_{e}+i-1<2d-1$. $\diamond$

It follows that also edge agents and path agents occupy pairwise disjoint
positions at all times. Therefore, the sequence
$s^{\prime}_{1},\dots,s^{\prime}_{2d}$ is feasible and $\langle
G^{\prime\prime},A,s^{\prime}_{0},t^{\prime},2d\rangle$ is a yes-instance of
MAPF.

For the reverse direction, assume that $\langle
G^{\prime\prime},A,s^{\prime}_{0},t^{\prime},2d\rangle$ is a yes-instance of
MAPF and let $s^{\prime}_{1},\dots,s^{\prime}_{2d}$ be the witnessing feasible
solution. Every path agent $a_{i}$ performs a walk starting in $s_{i}$ and
ending in $t_{i}$. We can see this walk as a subdivision of a path in $G$ that
we further transform into a path $P^{\prime}_{i}$ in $G$ by removing any
cycles and repeated vertices. It is easily seen that the length of
$P^{\prime}_{i}$ is at most $d$. Therefore, it suffices to show that
$P^{\prime}_{1},\dots,P^{\prime}_{k}$ are edge-disjoint.

######  Claim 7.

For every edge $e\in E$ of $G$, there exists at most one $c_{e}\in[2d-1]$ such
that the vertex $v_{e}=v_{e}^{2d-1}$ is not occupied by any agent of $B_{e}$
at time $c_{e}$.

Proof of the claim. For every agent $b_{e}^{i}$, the distance between
$s^{\prime}_{0}(b_{e}^{i})$ and $t^{\prime}(b_{e}^{i})$ is exactly $2d-1$ and
moreover, any walk other than the shortest path has length at least $2d+1$.
Therefore, the agent $b_{e}^{i}$ must advance by one step towards its target
in every turn up to one exception when he may remain stationary. As a
consequence, the edge agents $B_{e}$ do not leave the path $P_{e}$ and their
order along $P_{e}$ remains unchanged. In particular, they cannot swap.

Now, assume for a contradiction that there are two turns
$c_{e},c^{\prime}_{e}\in[2d-1]$ in which the vertex $v_{e}^{2d-1}$ is not
occupied by any agent of $B_{e}$. Without loss of generality, let
$c_{e}<c^{\prime}_{e}$. First, consider the agent $b_{e}^{2d-c_{e}-1}$. If it
moved without any delays, it would arrive at vertex $v_{e}^{2d-1}$ exactly at
time $c_{e}$. Thus, we have $s^{\prime}_{c_{e}}(b_{e}^{2d-c_{e}-1})=v_{e}^{j}$
where $j<2d-1$. On the other hand, if $j<2d-2$ then the agent
$b_{e}^{2d-c_{e}-1}$ cannot make it to its final destination
$v_{e}^{4d-c_{e}-2}$ in the remaining $2d-c_{e}$ turns. Therefore, it must be
that $s^{\prime}_{c_{e}}(b_{e}^{2d-c_{e}-1})=v_{e}^{2d-2}$. In fact, we can
show that $s^{\prime}_{c_{e}}(b_{e}^{i})=v_{e}^{i+c_{e}-1}$ for every
$i\in[2d-c_{e}-1]$. It holds since the edge agents in $B_{e}$ must keep their
relative order along $P_{e}$ and additionally, they cannot be more than
$2d-c_{e}$ steps away from their targets.

However, this also means that all the agents $b_{e}^{i}$ for
$i\in[2d-c_{e}-1]$ cannot make any further delays in order to reach their
targets in time. In particular, the agent $b_{e}^{2d-c^{\prime}_{e}}$ occupies
the vertex $v_{e}^{2d-1}$ at time $c^{\prime}_{e}$ which is a contradiction.
$\diamond$

It follows that at most one path agent can use the vertex $v_{e}$ throughout
all $2d$ turns. Therefore, the paths $P^{\prime}_{1},\dots,P^{\prime}_{k}$ are
edge-disjoint and $\langle G,s,t,k,d\rangle$ is a yes-instance of BEUP.

The described reduction together with [12] takes care of the cases when $p$ is
even. For odd $p\geq 20$, it is sufficient to perform the same reduction from
an instance $\langle G,s,t,k,\frac{p-1}{2}\rangle$ of BEUP and additionally,
attach a leaf $v_{a}$ to every original starting position $s^{\prime}_{0}(a)$
and set new a start $s^{\prime}_{0}(a)=v_{a}$. This modification does not
increase the cliquewidth of the graph $G^{\prime\prime}$ and it is
straightforward to prove its correctness. ∎

###  4.4 Maximum degree plus makespan

See 3

$v^{x}_{1,6}$$v^{x}_{1,1}$$v^{x}_{1,2}$$v^{x}_{1,3}$$v^{x}_{1,4}$$v^{x}_{2,6}$$v^{x}_{1,5}$$v^{x}_{2,1}$$v^{x}_{2,2}$$v^{x}_{2,3}$$v^{x}_{2,4}$$v^{x}_{2,5}$$v^{x}_{m,5}$$v^{x}_{m,6}$$v^{x}_{m,1}$$v^{x}_{m,2}$$v^{x}_{m,3}$$v^{x}_{m,4}$

(a) Variable gadget $G^{x}$, $m=m(x)$.

$v^{c}_{1,5}$$v^{c}_{1,4}$$v^{c}_{1,3}$$v^{c}_{1,2}$$v^{c}_{1,1}$$v^{c}_{2,2}$$v^{c}_{2,3}$$v^{c}_{2,4}$$v^{c}_{2,5}$$v^{c}_{2,1}$$v^{c}_{3,2}$$v^{c}_{3,3}$$v^{c}_{3,4}$$v^{c}_{3,5}$$v^{c}_{3,1}$$v^{c}_{t}$

(b) Clause gadget $H^{C}$.

Figure 4: The two gadgets used in the proof of Theorem 3. In subfigure (a),
the color red (blue resp.) is used on the vertices that may be incident to
clause gadgets, in which $x$ appear as a negative (positive resp.) literal.

###### Proof.

The problem is clearly in NP. To show that is is also NP-hard, we present a
reduction from the Planar $3$-SAT problem which is known to be NP-complete
[11]. In that problem, a 3CNF formula $\phi$ on $n$ variables and $m$ clauses
is given as an input. Let $X$ denote the set of variables appearing in $\phi$.
We say that a bipartite graph $G^{\prime}=(V,U,E)$ _corresponds_ to $\phi$ if
it is constructed from $\phi$ in the following way: for each variable
$x_{i}\in X$ add the _variable vertex_ $v_{i}$ in $V$ and for each clause
$C_{j}$ of $\phi$ add a _clause vertex_ $c_{j}$ in $U$. Then the edge
$v_{i}c_{j}$ is added if the variable $x_{i}$ appears in a literal of the
clause $C_{j}$. A 3CNF formula $\phi$ is valid as input to the Planar 3-SAT
problem if the graph $G^{\prime}$ that corresponds to $\phi$ is planar. The
question is whether there exists a truth assignment to the variables of $X$
satisfying $\phi$.

Our construction starts with a planar embedding of the bipartite graph
$G^{\prime}$ that corresponds to $\phi$. For each variable $x\in X$, let
$m(x)$ be the number clauses that contain $x$ or $\lnot x$. First, we replace
each clause vertex $c$ by $H^{c}$, which is a copy of the _clause gadget_ $H$
(illustrated in Figure 4(a)). Then, we replace each variable vertex $x$ by
$G^{x}$, a copy of the the _variable gadget_ $G^{x}$ (illustrated in Figure
4(b)). The superscripts $x$ and $c$ will be used to differentiate between the
vertices of the variable and clause gadgets respectively. Note that all the
edges of $G^{\prime}$ have been removed at this stage. So, for each edge $xc$
in $G^{\prime}$, we add two new edges connecting vertices of $G^{x}$ and
$H^{c}$. In particular, for each clause gadget $H^{c}$, we fix an arbitrary
ordering of the literals appearing in $C$. Then, for each $xc\in
E(G^{\prime})$, we assign (arbitrarily) an $i\in[m(x)]$ that hasn’t already
been assigned to a different literal appearing in $C$. Let $x$ be in the
$j$-th literal of $C$. If this literal is a positive one, then we add the
edges $v^{x}_{i,1}v^{c}_{j,1}$ and $v^{x}_{i,1}v^{c}_{j,5}$. Otherwise, we add
the edges $v^{x}_{i,3}v^{c}_{j,1}$ and $v^{x}_{i,3}v^{c}_{j,5}$. Let $G$ be
the resulting graph. Note here that the arbitrary choices made for these edges
will only impact the planarity of $G$. Thus, we will specify them in the final
stage of the proof.

We continue by defining the set of agents $A$ and the functions $s_{0}$ and
$t$. First, for each clause $C$, we create four _clause agents_ , three of
them denoted as $a^{c}_{i}$, $i\in[3]$, and the final as $a^{c}$. For
$i\in[3]$, we set $s_{0}(a^{c}_{i})=v^{c}_{i,1}$ and
$t(a^{c}_{i})=v^{c}_{i,4}$. Also, $s_{0}(a^{c})=v^{c}_{1,2}$ and
$t(a^{c})=v^{c}_{t}$. Next, for each variable $x$, we create $m(x)$ _variable
agents_ $a^{x}_{i}$, $i\in[m(x)]$. For each $i\in[m(x)]$, we set
$s_{0}(a^{x}_{i})=v^{x}_{i,2}$ and $t(a^{x}_{i})=v^{x}_{i,5}$. This completes
our construction. Observe that, for each $C$, if the agents $a^{c}_{i}$,
$i\in[3]$, move only through edges of $H^{c}$, then any feasible solution will
have a makespan of at least $4$.

We are now ready to show that $\phi$ is a yes-instance of Planar $3$-SAT if
and only if $\ell(\langle G,A,s_{0},t\rangle)\leq 3$. First, assume that we
have a satisfying assignment $\sigma$ for $\phi$. We will show that there
exists a feasible solution $s_{1},s_{2},s_{3}$ for $\langle
G,A,s_{0},t\rangle$. For each variable $x$ that appears in $m$ clauses, if
$\sigma(x)=true$ then, for all agents $a^{x}_{i}$, $i\in[m]$, we set
$s_{j}(a^{x}_{i})=v^{x}_{i,2+j}$ for all $j\in[3]$. Otherwise,
($\sigma(x)=false$), for all $i\in[m]$, we set $s_{1}(a^{x}_{i})=v^{x}_{i,1}$,
$s_{2}(a^{x}_{i})=v^{x}_{i,6}$ and $s_{3}(a^{x}_{i})=v^{x}_{i,5}$ (note that
$v^{x}_{1,6}=v^{x}_{m,4}$). Next, for each clause $C$, we deal with the agents
$a^{c}_{i}$, $i\in[3]$, and $a^{c}$. Since $\sigma$ is a satisfying
assignment, there exists at least one literal $x$ in $C$ that satisfies it.
W.l.o.g., assume that $x$ is the $j$-th literal of $C$. For the agents
$a^{c}_{i}$, $i\in[3]\setminus\\{j\\}$ we set $s_{1}(a^{c}_{i})=v^{c}_{i,2}$,
$s_{2}(a^{c}_{i})=v^{c}_{i,3}$ and $s_{3}(a^{c}_{i})=v^{c}_{i,4}$. For the
agent $a^{c}_{j}$, we set $s_{1}(a^{c}_{i})=u$, $s_{2}(a^{c}_{i})=v^{c}_{j,5}$
and $s_{3}(a^{c}_{i})=v^{c}_{j,4}$, where $u$ is the common neighbor of
$v^{c}_{j,1}$ and $v^{c}_{j,5}$ (which belongs in some variable gadget).
Finally, we define the movement of the agent $a^{c}$. If $j=1$ then we set
$s_{1}(a^{c})=v^{c}_{1,2}$, $s_{2}(a^{c})=v^{c}_{2,2}$ and
$s_{3}(a^{c})=v^{c}_{t}$. Otherwise, $s_{1}(a^{c})=v^{c}_{j,2}$,
$s_{2}(a^{c})=v^{c}_{t}$ and $s_{3}(a^{c})=v^{c}_{t}$.

Observe that for any agent $a\in A$, $s_{i}(a)$ is either a neighbor of
$s_{i-1}(a)$, or the same as $s_{i-1}(a)$. Therefore, it suffices to show that
no two agents are occupying the same vertex during the same turn. By the
definition of the sequence $s_{1},s_{2},s_{3}$, this may only happen between a
clause and a variable agent and only during the first turn. Let $a$ be a
clause agent that starts at a clause gadget $H^{c}$, and $s_{1}(a)=u\in
G^{x}$. Notice that, by the definition of $s$, the variable $x$ has received
by $\sigma$ a truth value such that the literal containing $x$ satisfies the
clause $C$. We consider two cases, either this literal is $x$ or $\neg x$. In
the first case, $\sigma(x)=true$; therefore, for all $i\in[m(x)]$,
$s_{1}(a^{x}_{i})=v^{x}_{i,3}$. Also, $s_{1}(a)=v^{x}_{i,1}$ since the
represented literal is a positive one and by the construction of $G$. In the
latter case, $\sigma(x)=false$; therefore, for all $i\in[m(x)]$,
$s_{1}(a^{x}_{i})=v^{x}_{i,1}$. Also, $s_{1}(a)=v^{x}_{i,3}$, since the
represented literal is a negative one and by the construction of $G$. In both
cases, there is no collision. This finishes the first direction of the
reduction.

For the reverse direction, we show that, if $\ell(\langle
G,A,s_{0},t\rangle)\leq 3$, then there exists a satisfying assignment of
$\phi$. We start with some observations.

######  Observation 2.

In any solution of makespan $3$, any agent $a\in A\setminus\\{a^{c}\mid
c\in\phi\\}$ must move through a shortest path between $s_{0}(a)$ and $t(a)$.

Indeed, for any agent in the given set, the distance between its starting and
terminal positions is exactly $3$.

######  Observation 3.

Let $A_{x}$ be the set of agents $\\{a^{x}_{i}\mid i\in[m(x)]\\}$ for a
variable $x$. In any solution of makespan $3$ either
$(s_{1}(a^{x}_{i}),s_{2}(a^{x}_{i}),s_{3}(a^{x}_{i}))=(v_{i,3}^{x},v_{i,4}^{x},v_{i,5}^{x})$
for all $i\in[m(x)]$ or
$(s_{1}(a^{x}_{i}),s_{2}(a^{x}_{i}),s_{3}(a^{x}_{i}))=(v_{i,1}^{x},v_{i,6}^{x},v_{i,5}^{x})$
for all $i\in[m(x)]$ (recall that $v_{i,6}^{x}=v_{m,4}$ for $m=m(x)$).

Indeed, if this were not true, then there would exist an
$i\in[m(x)]\setminus\\{1\\}$ such that $s_{2}(a^{x}_{i})=s_{2}(a^{x}_{i-1})$,
or $s_{2}(a^{x}_{1})=s_{2}(a^{x}_{m})$, for $m=m(x)$.

######  Observation 4.

For any clause $C$, at most two of the agents $a^{c}_{i}$, $i\in[3]$, can have
$s(a^{c}_{i})=v^{c}_{i,2}$.

This follows directly from the fact that if the agents of $H^{c}$ move only
through edges of $H^{c}$, then any feasible solution will have a makespan of
at least $4$. In other word, at least one clause agent of each clause must
move through the vertices of a variable gadgets.

We define the following assignment: let $x$ be a variable; we set $x$ to be
true if $s_{1}(a^{x}_{1})=v^{x}_{1,3}$ and false otherwise. This assignment
satisfies $\phi$. Indeed, consider a clause $C$. We know that there exists a
$j\in[3]$ such that $a^{c}_{j}$ moves through a vertex $u$ belonging in
$G^{x}$. There are two cases to be analysed.

Case 1 ($\boldsymbol{u=v^{x}_{i,1}}$): In this case, by construction, we know
that $x$ appears positively in the clause $C$. From the previous observations,
it follows that $s_{1}(a^{c}_{j})=u=v^{x}_{i,1}$ and thus
$s_{1}(a^{x}_{i})=u=v^{x}_{i,3}$. Therefore, $s_{1}(a^{x}_{1})=u=v^{x}_{1,3}$
and $x$ has been set to true.

Case 2 ($\boldsymbol{u=v^{x}_{i,3}}$): In this case, by construction, we know
that $x$ appears negatively in the clause $C$. From the previous observations,
it follows that $s_{1}(a^{c}_{j})=u=v^{x}_{i,3}$ and thus
$s_{1}(a^{x}_{i})=u=v^{x}_{i,1}$. Therefore, $s_{1}(a^{x}_{1})=u=v^{x}_{1,1}$
and $x$ has been set to false.

In both cases above, the clause $C$ is satisfied. In other words, the
assignment we defined is indeed satisfying $\phi$.

Lastly, it remains to argue about the planarity of $G$.

######  Claim 8.

The graph $G$ can be constructed so that it is planar.

Proof of the claim. In order to draw a planar embedding of $G$, we start from
a planar emending of $G^{\prime}$. Imagine that around each vertex of
$G^{\prime}$ we have a circle that is small enough so that no two such circles
intersect. We may also assume that the edges of $G^{\prime}$ are drawn in such
a way so that each edge intersects every such circle at most once. We will say
that the area inside any such circle is _close_ to the corresponding vertex
and the area not included in any cycle is _far_ from the vertices.

First, when we replace the vertices with gadgets, we draw them inside the
corresponding circles, and as they are drawn in Figure 4. We also need to draw
the new edges. Recall that each edge of $G^{\prime}$ has been replaced by two
new edges in $G$. We draw the new edges so that their parts that lie far from
the vertices are parallel to the original edges. That way, and since
$G^{\prime}$ is planar, no two of the new edges are crossing in the area far
from the vertices.

Before we deal with the part of the new edges that lies in the area close to
the vertices (defined by the aforementioned circles) we will define, for each
gadget (regardless of it being a variable or a clause gadget) an ordering of
the edges that need to be attached to its vertices. We proceed as follows. For
each vertex of $G$, consider the center of its circle. We define a ray $\mu$
that starts from this center and moves horizontally to the right of it. We
enumerate the edges $e_{1},\dots,e_{m}$ of $G^{\prime}$ based on their
entering points on this circle (i.e., the intersection of the original edges
and the circles around the original vertices in $G^{\prime}$). In particular,
we follow the order in which $\mu$ meets the entering points of the edges when
it moves counter clockwise. Let us denote the edges that replace the edge
$e_{i}$ (for any $i\in[m]$) by $e_{i,1}$ and $e_{i,2}$. We decide the vertices
of the gadget to which these edges will be incident based on $i$. When we
consider a variable gadget, $e_{i,1}$ and $e_{i,2}$ will be incident to
$v^{x}_{i,1}$ if the corresponding literal is a positive one and to
$v^{x}_{i,3}$ otherwise (as described in the initial construction of $G$).
Similarly, when we consider a clause gadget, $e_{i,1}$ and $e_{i,2}$ will be
incident to $v^{c}_{i,1}$ and $v^{c}_{i,5}$ respectively.

To show that we can draw the new edges so they do not cross in the area close
to the circles, it suffices to observe that:

######  Observation 5.

Consider two concentric circles. Let $p_{1},\ldots,p_{i}$ be $i\geq 1$
vertices on the outside circle in a counter-clockwise order. Also, let
$p^{\prime}_{1},\ldots,p^{\prime}_{i}$ be $i$ vertices on the inside circle in
a counter-clockwise order. Then, we can draw all the edges
$p_{i}p^{\prime}_{i}$ such that all of then are in the area between the two
circles and no two of them are crossing.

This completes the proof of the claim. $\diamond$ ∎

See 4

$u^{x}_{1,1}$$w^{x}_{1}$$u^{x}_{1,3}$$u^{x}_{1,2}$$u^{x}_{1,4}$$u^{x}_{1,5}$$v^{x}_{1,1}$$v^{x}_{1,3}$$v^{x}_{1,2}$$v^{x}_{1,4}$$v^{x}_{1,5}$$v^{x}_{1,1}$$w^{x}_{1}$$v^{x}_{1,3}$$v^{x}_{1,2}$$v^{x}_{1,4}$$v^{x}_{1,5}$$u^{x}_{1,1}$$u^{x}_{1,3}$$u^{x}_{1,2}$$u^{x}_{1,4}$$u^{x}_{1,5}$$v^{x}_{m,1}$$w^{x}_{m}$$v^{x}_{m,3}$$v^{x}_{m,2}$$v^{x}_{m,4}$$v^{x}_{m,5}$$u^{x}_{m,1}$$u^{x}_{m,3}$$u^{x}_{m,2}$$u^{x}_{m,4}$$u^{x}_{m,5}$

(a) Variable gadget $G^{x}$, $m=m(x)$.

$v^{c}_{1,3}$$v^{c}_{1,2}$$v^{c}_{1,1}$$v^{c}_{2,2}$$v^{c}_{2,3}$$v^{c}_{2,1}$$v^{c}_{3,2}$$v^{c}_{3,3}$$v^{c}_{3,1}$

(b) Clause gadget $H^{C}$.

Figure 5: The two gadgets used in the proof of Theorem 4. In subfigure (a),
the color red (blue resp.) is used on the vertices that may be incident to
clause gadgets, in which $x$ appear as a negative (positive resp.) literal.

###### Proof.

The proof is similar to that of Theorem 3. The problem is clearly in . To show
that is is also NP-hard, we present a reduction from the Planar $3$-SAT. As
before, we assume that we have the 3CNF formula $\phi$ on $n$ variables and
$m$ clauses. We denote with $X$ the set of variables appearing in $\phi$.
Also, let $G^{\prime}=(V,U,E)$ be the bipartite graph that _corresponds_ to
$\phi$.

Our construction starts with a planar embedding of the bipartite graph
$G^{\prime}$ that corresponds to $\phi$. For each variable $x\in X$, let
$m(x)$ be the number of clauses that contain $x$ or $\lnot x$. First, we
replace each clause vertex $c$ by $H^{c}$, which is a copy of the _clause
gadget_ $H$ (illustrated in Figure 5(a)). Then, we replace each variable
vertex $x$ by $G^{x}$, a copy of the the _variable gadget_ $G^{x}$
(illustrated in Figure 5(b)). The superscripts $x$ and $c$ will be used to
differentiate between the vertices of the variable and clause gadgets
respectively. Note that all the edges of $G^{\prime}$ have been removed at
this stage. So, for each edge $xc$ in $G^{\prime}$, we add two new edges
connecting vertices of $G^{x}$ and $H^{c}$. In particular, to each $xc\in
E(G^{\prime})$, we assign an $i\in[m(x)]$ that hasn’t already been assigned to
a different appearance of $x$ in $\phi$. Let $x$ be in the $j$-th literal of
$C$. If this literal is a positive one, then we add the edges
$u^{x}_{i,2}v^{c}_{j,1}$ and $u^{x}_{i,2}v^{c}_{j,3}$. Otherwise, we add the
edges $v^{x}_{i,2}v^{c}_{j,1}$ and $v^{x}_{i,2}v^{c}_{j,3}$. Let $G$ be the
resulting graph.

We continue by defining the set of agents $A$ and the functions $s_{0}$ and
$t$. First, for each clause $C$, we create three _clause agents_ denoted as
$a^{c}_{i}$, $i\in[3]$. For $i\in[3]$, we set $s_{0}(a^{c}_{i})=v^{c}_{i,1}$
and $t(a^{c}_{i})=v^{c}_{i,3}$. Then, for each clause $C$, we create four
_clause agents_ , three of them denoted as $a^{c}_{i}$, $i\in[3]$, and the
final as $a^{c}$. For $i\in[3]$, we set $s_{0}(a^{c}_{i})=v^{c}_{i,1}$ and
$t(a^{c}_{i})=v^{c}_{i,3}$. Also, $s_{0}(a^{c})=v^{c}_{1,2}$ and
$t(a^{c})=v^{c}_{2}$. Next, for each variable $x$, we create $4m(x)$ _variable
agents_ $a^{x}_{i,j}$ and $b^{x}_{i,j}$, $i\in[m(x)]$ and $j\in[2]$. For each
$i\in[m(x)]$, we set $s_{0}(a^{x}_{i,1})=v^{x}_{i,1}$,
$s_{0}(b^{x}_{i,1})=u^{x}_{i,1}$, $s_{0}(a^{x}_{i,2})=v^{x}_{i,4}$ and
$s_{0}(b^{x}_{i,2})=u^{x}_{i,4}$. Finally, for each $i\in[m(x)]$, we set
$t(a^{x}_{i,1})=v^{x}_{i,3}$, $t(b^{x}_{i,1})=u^{x}_{i,3}$,
$t(a^{x}_{i,2})=v^{x}_{i,2}$ and $t(b^{x}_{i,2})=u^{x}_{i,2}$. This completes
our construction. Observe that, for each $C$, since we are not allowing swaps,
if the agents $a^{c}_{i}$, $i\in[3]$, move only through edges of $H^{c}$, then
any feasible solution will have a makespan of at least $3$.

We are now ready to show that $\phi$ is a yes-instance of Planar $3$-SAT if
and only if $\langle G,A,s_{0},t,2\rangle$ is a yes-instance of Multiagent
Path Finding No Swaps. First, assume that we have a satisfying assignment
$\sigma$ for $\phi$. We will show that there exists a feasible solution
$s_{1},s_{2}$ for $\langle G,A,s_{0},t,2\rangle$. For each variable $x$ that
appears in $m$ clauses, if $\sigma(x)=true$ then, for all agents $a^{x}_{i,j}$
and $b^{x}_{i,j}$, $i\in[m]$ and $j\in[2]$, we set:

    * –

$s_{1}(a^{x}_{i,1})=v^{x}_{i,2}$ and $s_{2}(a^{x}_{i,1})=v^{x}_{i,3}$

    * –

$s_{1}(b^{x}_{i,1})=w^{x}_{i}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,3}$

    * –

$s_{1}(a^{x}_{i,2})=v^{x}_{i,5}$ and $s_{2}(a^{x}_{i,2})=v^{x}_{i,2}$

    * –

$s_{1}(b^{x}_{i,2})=v^{x}_{i,3}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,2}$

Otherwise, ($\sigma(x)=false$), for all $i\in[m]$, we set:

    * –

$s_{1}(a^{x}_{i,1})=w^{x}_{i}$ and $s_{2}(a^{x}_{i,1})=v^{x}_{i,3}$

    * –

$s_{1}(b^{x}_{i,1})=u^{x}_{i,2}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,3}$

    * –

$s_{1}(a^{x}_{i,2})=v^{x}_{i,3}$ and $s_{2}(a^{x}_{i,2})=v^{x}_{i,2}$

    * –

$s_{1}(b^{x}_{i,2})=v^{x}_{i,5}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,2}$

Note that, for any $i\in[m]$, $v^{x}_{i,5}=u^{x}_{k,5}$ where $k=1+(i\mod m)$.
Therefore, no two agents occupy the same vertex during the same turn. Next,
for each clause $C$, we deal with the agents $a^{c}_{i}$, $i\in[3]$, and
$a^{c}$. Since $\sigma$ is a satisfying assignment, there exists at least one
literal $\lambda$ in $C$ that satisfies it. W.l.o.g., assume that $x$ is the
variable that appears in $\lambda$ and that $\lambda$ in $j$-th literal of
$C$. For the agents $a^{c}_{i}$, $i\in[3]\setminus\\{j\\}$ we set
$s_{1}(a^{c}_{i})=v^{c}_{i,2}$ and $s_{2}(a^{c}_{i})=v^{c}_{i,3}$. For the
agent $a^{c}_{j}$, we set $s_{1}(a^{c}_{i})=u$ and
$s_{2}(a^{c}_{i})=v^{c}_{j,5}$, where $u$ is the common neighbor of
$v^{c}_{j,1}$ and $v^{c}_{j,3}$ (which belongs in the variable gadget of $x$).
Finally, we define the movement of the agent $a^{c}$. We set
$s_{1}(a^{c})=v^{c}_{j,2}$ and $s_{2}(a^{c})=v^{c}_{2,2}$.

Observe that for any agent $a\in A$, $s_{i}(a)$ is either a neighbor of
$s_{i-1}(a)$, or the same as $s_{i-1}(a)$. Therefore, it suffices to show that
no two agents are occupying the same vertex during the same turn. By the
definition of the sequence $s_{1},s_{2}$, this may only happen between a
clause and a variable agent and only during the first turn. Let $a$ be a
clause agent that starts at a clause gadget $H^{c}$, and $s_{1}(a)=u\in
G^{x}$. Notice that, by the construction of the solution, $\sigma(x)$ is such
that the literal $\lambda$ containing $x$ satisfies the clause $C$. We
consider two cases, either this literal is $\lambda=x$ or $\lambda=\neg x$. In
the first case, $\sigma(x)=true$; therefore, for all $i\in[m(x)]$, no agent
occupies the vertex $u^{x}_{i,2}$. Also, $s_{1}(a)=u^{x}_{i,2}$ since the
represented literal is a positive one and by the construction of $G$. In the
latter case, $\sigma(x)=false$; therefore, for all $i\in[m(x)]$, no agent
occupies the vertex $v^{x}_{i,2}$. Also, $s_{1}(a)=v^{x}_{i,2}$, since the
represented literal is a negative one and by the construction of $G$. In both
cases, there is no collision. This finishes the first direction of the
reduction.

For the reverse direction, we show that, if $s_{1},s_{2}$ is a solution of
$\langle G,A,s_{0},t,2\rangle$, then there exists a satisfying assignment of
$\phi$. We start with some observations.

######  Observation 6.

In any solution of makespan $2$, any agent $a\in A\setminus\\{a^{c}\mid
c\in\phi\\}$ must move through a shortest path between $s_{0}(a)$ and $t(a)$.

Indeed, for any agent in the given set, the distance between its starting and
terminal positions is exactly $2$.

######  Claim 9.

Let $A_{x}$ be the set of agents $\\{a^{x}_{i},b^{x}_{i}\mid i\in[m(x)]\\}$
for a variable $x$. In any solution of makespan $2$ either, for all
$i\in[m(x)]$,:

    * –

$s_{1}(a^{x}_{i,1})=v^{x}_{i,2}$ and $s_{2}(a^{x}_{i,1})=v^{x}_{i,3}$

    * –

$s_{1}(b^{x}_{i,1})=w^{x}_{i}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,3}$

    * –

$s_{1}(a^{x}_{i,2})=v^{x}_{i,5}$ and $s_{2}(a^{x}_{i,2})=v^{x}_{i,2}$

    * –

$s_{1}(b^{x}_{i,2})=v^{x}_{i,3}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,2}$

or, for all $i\in[m(x)]$,:

    * –

$s_{1}(a^{x}_{i,1})=w^{x}_{i}$ and $s_{2}(a^{x}_{i,1})=v^{x}_{i,3}$

    * –

$s_{1}(b^{x}_{i,1})=u^{x}_{i,2}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,3}$

    * –

$s_{1}(a^{x}_{i,2})=v^{x}_{i,3}$ and $s_{2}(a^{x}_{i,2})=v^{x}_{i,2}$

    * –

$s_{1}(b^{x}_{i,2})=u^{x}_{i,5}$ and $s_{2}(b^{x}_{i,1})=u^{x}_{i,2}$

Proof of the claim. Consider the movement of any agent $a^{x}_{i,1}$ and
observe how this affects the rest of the agents. W.l.o.g. assume that, for
some $i\in[m(x)]$, $a^{x}_{i,1}$ moves through $v^{x}_{i,2}$. We will show
that:

    * –

$s_{1}(a^{x}_{i,2})=v^{x}_{i,5}$,

    * –

$s_{1}(b^{x}_{k,1})=u^{x}_{k,3}$,

    * –

$s_{1}(b^{x}_{k,1})=w^{x}_{k}$ and

    * –

$s_{1}(a^{x}_{k,1})=v^{x}_{k,2}$,

where $k=1+(i\mod m)$.

Notice that $s_{1}(a^{x}_{i,1})=v^{x}_{i,2}$ forces that
$s_{1}(a^{x}_{i,2})=v^{x}_{i,5}$, as otherwise we would not achieve a solution
of makespan $2$. Similarly, since $v^{x}_{i,5}=u^{x}_{k,5}$, we have that
$s_{1}(b^{x}_{k,1})=u^{x}_{k,3}$. This gives us that
$s_{1}(b^{x}_{k,1})=w^{x}_{k}$ and, finally, $s_{1}(a^{x}_{k,1})=v^{x}_{k,2}$.
Then, the $s_{2}$ follows.

Similarly, we can show that $s_{1}(a^{x}_{i,1})=w^{x}_{i}$ forces the second
set of moves. $\diamond$

######  Observation 7.

For any clause $C$, at most two of the agents $a^{c}_{i}$, $i\in[3]$, can have
$s(a^{c}_{i})=v^{c}_{i,2}$.

This follows directly from the fact that if the agents of $H^{c}$ move only
through edges of $H^{c}$, then any feasible solution will have a makespan of
at least $3$. In other words, at least one clause agent of each clause must
move through the vertices of a variable gadgets.

We define the following truth assignment. Let $x$ be a variable; we set $x$ to
be true if $s_{1}(a^{x}_{1,1})=v^{x}_{1,2}$ and false otherwise. This
assignment satisfies $\phi$. Indeed, consider a clause $C$. We know that there
exists at least one $j\in[3]$ such that $a^{c}_{j}$ moves through a vertex $u$
belonging in $G^{x}$, for a variable $x$. There are two cases to be analysed.

Case 1 ($\boldsymbol{u=u^{x}_{i,2}}$): In this case, by construction, we know
that $x$ appears positively in the clause $C$. From the previous observations,
it follows that $s_{1}(a^{c}_{j})=u=u^{x}_{i,2}$ and thus
$s_{1}(b^{x}_{i,1})=w^{x}_{i}$ (as it can not be $u^{x}_{i,2}$). Therefore, by
Claim 9, $s_{1}(a^{x}_{1,1})=v^{x}_{1,2}$ and $x$ has been set to true.

Case 2 ($\boldsymbol{u=v^{x}_{i,2}}$): In this case, by construction, we know
that $x$ appears negatively in the clause $C$. From the previous observations,
it follows that $s_{1}(a^{c}_{j})=u=v^{x}_{i,2}$ and thus
$s_{1}(a^{x}_{i,1})=w^{x}_{i}$. Therefore, by Claim 9,
$s_{1}(a^{x}_{1,1})=w^{x}_{1}$ and $x$ has been set to false.

In both cases above, the clause $C$ is satisfied. In other words, the
assignment we defined is indeed satisfying $\phi$.

The planarity of the graph $G$ follows from exactly the same arguments as
these in proof of Theorem 3. ∎

##  5 Conclusion

In this paper we studied the parameterised complexity of the Multiagent Path
Finding problem. The main takeaway message is that the problem is rather
intractable. Indeed, the problem remains hard even on trees. Hence, the
treewidth of the input graph is highly unlikely to yield an efficient
algorithm (under standard theoretical assumptions). This suggests that the
current heuristic-oriented approach followed by the community is, in some
sense, optimal. On the positive side, we showed that there are various
combinations of parameters that lead to efficient algorithms, such as the
number of agents plus the makespan. These positive results could potentially
lead to improvements in practice, which should be the subject of a dedicated
future study. The first step towards this direction is to check whether our
algorithms can be utilised in tandem with some state-of-the-art heuristic
algorithm, in order to obtain an improved result.

## References

    * [1] O. Aichholzer, E. D. Demaine, M. Korman, A. Lubiw, J. Lynch, Z. Masárová, M. Rudoy, V. V. Williams, and N. Wein.  Hardness of token swapping on trees.  In S. Chechik, G. Navarro, E. Rotenberg, and G. Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
    * [2] R. Barták, J. Švancara, and M. Vlk.  A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs.  In E. André, S. Koenig, M. Dastani, and G. Sukthankar, editors, Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 748–756. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018.
    * [3] H. L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.
    * [4] D. G. Corneil and U. Rotics.  On the relationship between clique-width and treewidth.  SIAM J. Comput., 34(4):825–847, 2005.
    * [5] B. Courcelle and S. Olariu.  Upper bounds to the clique width of graphs.  Discret. Appl. Math., 101(1-3):77–114, 2000.
    * [6] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
    * [7] R. G. Downey and M. R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
    * [8] E. Eiben, R. Ganian, and I. Kanj.  The parameterized complexity of coordinated motion planning.  In E. W. Chambers and J. Gudmundsson, editors, 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volume 258 of LIPIcs, pages 28:1–28:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
    * [9] J. Flum and M. Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
    * [10] R. Ganian, P. Hlinený, J. Nesetril, J. Obdrzálek, and P. O. de Mendez.  Shrub-depth: Capturing height of dense graphs.  Log. Methods Comput. Sci., 15(1), 2019.
    * [11] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman, 1979.
    * [12] P. A. Golovach and D. M. Thilikos.  Paths of bounded length and their cuts: Parameterized complexity and algorithms.  Discret. Optim., 8(1):72–86, 2011.
    * [13] P. E. Hart, N. J. Nilsson, and B. Raphael.  A formal basis for the heuristic determination of minimum cost paths.  IEEE Trans. Syst. Sci. Cybern., 4(2):100–107, 1968.
    * [14] A. J. Hoffman and R. R. Singleton.  On moore graphs with diameters 2 and 3.  IBM J. Res. Dev., 4(5):497–504, 1960.
    * [15] T. Kloks.  Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science.  Springer, 1994.
    * [16] T. Korhonen and D. Lokshtanov.  An improved parameterized algorithm for treewidth.  In B. Saha and R. A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 528–541. ACM, 2023.
    * [17] J. Li, A. Tinka, S. Kiesel, J. W. Durham, T. K. S. Kumar, and S. Koenig.  Lifelong multi-agent path finding in large-scale warehouses.  In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 11272–11281. AAAI Press, 2021.
    * [18] W. Lochet.  A polynomial time algorithm for the _k_ -disjoint shortest paths problem.  In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 169–178. SIAM, 2021.
    * [19] H. Ma, C. A. Tovey, G. Sharon, T. K. S. Kumar, and S. Koenig.  Multi-agent path finding with payload transfers and the package-exchange robot-routing problem.  In D. Schuurmans and M. P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 3166–3173. AAAI Press, 2016.
    * [20] H. Ma, J. Yang, L. Cohen, T. K. S. Kumar, and S. Koenig.  Feasibility study: Moving non-homogeneous teams in congested video game environments.  In B. Magerko and J. P. Rowe, editors, Proceedings of the Thirteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-17), October 5-9, 2017, Snowbird, Little Cottonwood Canyon, Utah, USA, pages 270–272. AAAI Press, 2017.
    * [21] R. Morris, C. S. Pasareanu, K. S. Luckow, W. Malik, H. Ma, T. K. S. Kumar, and S. Koenig.  Planning, scheduling and monitoring for airport surface operations.  In D. Magazzeni, S. Sanner, and S. Thiébaux, editors, Planning for Hybrid Systems, Papers from the 2016 AAAI Workshop, Phoenix, Arizona, USA, February 13, 2016, volume WS-16-12 of AAAI Technical Report. AAAI Press, 2016.
    * [22] J. Nesetril and P. O. de Mendez.  Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics.  Springer, 2012.
    * [23] R. Niedermeier.  Invitation to Fixed-Parameter Algorithms.  Oxford University Press, 2006.
    * [24] P. Scheffler.  A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree Width.  Fachbereich Mathematik: Preprint-Reihe Mathematik. Techn. Univ., 1994\.
    * [25] J. Snape, S. J. Guy, J. van den Berg, M. C. Lin, and D. Manocha.  Reciprocal collision avoidance and multi-agent navigation for video games.  In A. Felner, N. R. Sturtevant, K. E. Bekris, and R. Stern, editors, Multiagent Pathfinding, Papers from the 2012 AAAI Workshop, MAPF@AAAI 2012, Toronto, Ontario, Canada, July 22, 2012, volume WS-12-10 of AAAI Technical Report. AAAI Press, 2012.
    * [26] R. Stern.  Multi-Agent Path Finding - An Overview, volume 11866 of Lecture Notes in Computer Science, pages 96–115.  Springer, 2019.
    * [27] R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, R. Barták, and E. Boyarski.  Multi-agent pathfinding: Definitions, variants, and benchmarks.  In P. Surynek and W. Yeoh, editors, Proceedings of the Twelfth International Symposium on Combinatorial Search, SOCS 2019, Napa, California, 16-17 July 2019, pages 151–159. AAAI Press, 2019.
    * [28] P. Surynek.  An optimization variant of multi-robot path planning is intractable.  In M. Fox and D. Poole, editors, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010.
    * [29] P. Surynek.  Lazy compilation of variants of multi-robot path planning with satisfiability modulo theory (SMT) approach.  In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2019, Macau, SAR, China, November 3-8, 2019, pages 3282–3287. IEEE, 2019.
    * [30] P. Surynek.  Continuous multi-agent path finding via satisfiability modulo theories (SMT).  In A. P. Rocha, L. Steels, and H. J. van den Herik, editors, Agents and Artificial Intelligence, 12th International Conference, ICAART 2020, Valletta, Malta, February 22-24, 2020, Revised Selected Papers, volume 12613 of Lecture Notes in Computer Science, pages 399–420. Springer, 2020\.
    * [31] P. Surynek, J. Švancara, A. Felner, and E. Boyarski.  Integration of independence detection into sat-based optimal multi-agent path finding - A novel sat-based optimal MAPF solver.  In H. J. van den Herik, A. P. Rocha, and J. Filipe, editors, Proceedings of the 9th International Conference on Agents and Artificial Intelligence, ICAART 2017, Volume 2, Porto, Portugal, February 24-26, 2017, pages 85–95. SciTePress, 2017.
    * [32] M. M. Veloso, J. Biswas, B. Coltin, and S. Rosenthal.  Cobots: Robust symbiotic autonomous mobile service robots.  In Q. Yang and M. J. Wooldridge, editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, page 4423. AAAI Press, 2015.
    * [33] P. R. Wurman, R. D’Andrea, and M. Mountz.  Coordinating hundreds of cooperative, autonomous vehicles in warehouses.  AI Mag., 29(1):9–20, 2008.
    * [34] J. Yu.  Intractability of optimal multirobot path planning on planar graphs.  IEEE Robotics Autom. Lett., 1(1):33–40, 2016.