Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Argyrios Deligkas Eduard Eiben Robert Ganian Iyad Kanj M. S. Ramanujan


 






 
 










  









 


















arrows



 
 
 


 
 
 
plain
 

subcase[theorem]SubCase
transrule[theorem]TransRule
branchrule[theorem]BranchRule
ourremark[theorem]Remark

 

assumption[theorem]Assumption
 fact[theorem]Fact
reductionReduction Rules[section]

longtheoremTheorem
longlemma[longtheorem]Lemma
longproposition[longtheorem]Proposition
longdefinition[longtheorem]Definition
longobservation[longtheorem]Observation
ourclaimClaim

definition
our_definition[theorem]Definition















































 













calc








GrayBox[1]
   
    #1
    
       
   
       
    
    
    
       (Text)[draw=black!90,fill=white,rounded corners,
             inner sep=2ex,text width=]
             ;
        (x) at (current bounding box.north west);
        [draw=white,rectangle,inner sep=3pt,anchor=north west,fill=white] 
        at ((x)+(6pt,.75em)) ;
    
    

        

problem[2][]=8pt
                                =0pt
                

                #1
                  #2
                

                
                
                
                          
                
            
                
                
                

                 
 
plainurl
       
  Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy 
 


Department of Computer Science, Royal Holloway, University of London, Egham, UKArgyrios.Deligkas@rhul.ac.ukhttps://orcid.org/0000-0002-6513-6748Supported by Engineering and Physical Sciences Research Council (EPSRC) grant EP/X039862/1.

Department of Computer Science, Royal Holloway, University of London, Egham, UKeduard.eiben@rhul.ac.ukhttps://orcid.org/0000-0003-2628-3435

Algorithms and Complexity Group, TU Wien, Vienna, Austriarganian@gmail.comhttps://orcid.org/0000-0002-7762-8045Project No. Y1329 of the Austrian Science Fund (FWF), Project No. ICT22-029 of the Vienna Science Foundation (WWTF).

School of Computing, DePaul University, Chicago, USAikanj@cdm.depaul.edu0000-0003-1698-8829DePaul URC Grants 606601 and 350130
Department of Computer Science, University of Warwick, UKR.Maadapuzhi-Sridharan@warwick.ac.ukhttps://orcid.org/0000-0002-2116-6048 Supported by Engineering and Physical Sciences Research Council (EPSRC) grants EP/V007793/1 and EP/V044621/1.

  
 

A. Deligkas, E. Eiben, R. Ganian, I. Kanj, R. M. Sridharan  
A. Deligkas, E. Eiben, R. Ganian, I. Kanj, R. M. Sridharan 
 
[300]Theory of computation Parameterized complexity and exact algorithms

  
   




  



Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
    M. S. Ramanujan
    April 29, 2024
===========================================================================


We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. 


 We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle; and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. 
The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids.

We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids  under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth – a class including, among others, all graphs of bounded genus.
 
          
     
  
  

§ INTRODUCTION

The task of routing a set of robots (or agents) from their initial positions to specified destinations while avoiding collisions is of great importance in a multitude of different settings. Indeed, there is an extensive body of works dedicated to algorithms solving this task, especially in the computational geometry <cit.>, artificial intelligence <cit.> and robotics <cit.> research communities. Such algorithms typically aim at providing a schedule for the robots which is not only safe (in the sense of avoiding collisions), but which also optimizes a certain measure of the schedule – typically its makespan or energy (i.e., the total distance traveled by all robots). In this article, we focus solely on the task of optimizing the latter of these two measures.

  
A common formalization of our task of interest is given by the Coordinated Motion Planning problem (also known as Multiagent Pathfinding). In the context of energy minimization, the problem can be stated as follows: Given a graph G, a budget ℓ and a set  of robots, each equipped with an initial vertex and destination vertex in G, compute a schedule which delivers all the robots to their destinations while ensuring that the combined length traveled of all the robots is at most ℓ. Here, a schedule can be seen as a sequence of commands to the robots, where at every time step each of the robots can move to an adjacent vertex as long as no vertex or edge is used by more than a single robot at that time step. Coordinated Motion Planning, which generalizes the famous -hard (n^2-1)-puzzle <cit.>, has been extensively studied—both in the discrete setting considered here as well as in various continuous settings <cit.>—
and has also been the target of specific computing challenges <cit.>.
  In other variants of the problem, there is no requirement to route all the robots to their destinations – sometimes the majority (or all but 1) of the robots are simply movable obstacles that do not have destinations of their own. This is captured, e.g., by the closely-related and well-studied Rush Hour puzzle/problem <cit.> and by Graph Motion Planning with 1 Robot (GCMP1) <cit.>, which both feature a single robot with a designated destination.
  
Both Coordinated Motion Planning and GCMP1 are known to be -hard <cit.>. While several works have already studied Coordinated Motion Planning in the context of approximation and classical complexity theory, a more fine-grained investigation of the difficulty of finding optimal schedules through the lens of parameterized complexity <cit.> was only carried out recently <cit.>. 
 The work in <cit.> established the fixed-parameter tractability[A problem is fixed-parameter tractable w.r.t. a parameter k if it can be solved in time f(k)· n^(1), where n is the input size and f is a computable function.] of Coordinated Motion Planning parameterized by either the number k of robots or the budget ℓ (as well as the makespan variant when parameterized by k), but only on solid grids; a solid grid is a standard rectangular p × q grid (i.e., with no holes), for some p, q ∈. The more recent work in <cit.> showed the [1]-hardness of the makespan variant of Coordinated Motion Planning w.r.t. the number of robots. The paper <cit.> also showed the -hardness of the makespan problem-variant on trees, and presented parameterized complexity results with respect to several combinations of parameters.  
In this article, we focus our attention on GCMP <cit.>, which generalizes both Coordinated Motion Planning and GCMP1 by allowing an arbitrary partitioning of the robots into those with destinations and those which act merely as movable obstacles[While previous hardness results for GCMP considers serial motion of robots (e.g.,  <cit.>), the hardness applies to parallel motion as well. Here we obtain algorithms for the coordinated motion variant with parallel movement, but note that the results can be directly translated to the serial version.].

 
Contribution.  The aim of this article is to push our understanding of the parameterized complexity of finding energy-optimal schedules beyond the class of solid grids. While this aim was already highlighted in the aforementioned paper on solid grids <cit.>, the techniques used there are highly specific to that setting and it is entirely unclear how one could generalize them even to the setting of subgrids; a subgrid is a subgraph of a solid grid and we define its height to be the minimum of its two dimensions.

 As our two main contributions, we provide novel fixed-parameter algorithms (1) for GCMP1 parameterized by the number of robots alone (Theorem <ref>), and (2) for GCMP parameterized by the number of robots plus the treewidth of the graph (Theorem <ref>). Theorem <ref> implies, as a corollary, the fixed-parameter tractability of  parameterized by k plus the minimum dimension of the subgrid.
  
theoremfptrushhour

   is  parameterized by the number k of robots.

theoremfptrushhour

   is  parameterized by the number k of robots.







theoremfpttw

	 is  parameterized by the number of robots and the treewidth of the input graph. 




The main technical tool we use to obtain both of these results is a novel fixed-parameter approximation algorithm for Generalized Coordinated Motion Planning parameterized by k alone, where the approximation error is only additive in k. We believe this result – summarized in Theorem <ref> below – to be of independent interest.

theoremfptapxcorollary

 There is an  approximation algorithm for  parameterized by the number k of robots which guarantees an additive error of (k^5). 

theoremfptapxcorollary

 There is an  approximation algorithm for  parameterized by the number k of robots which guarantees an additive error of (k^5). 



 The proof of Theorem <ref> builds upon Theorem <ref>. 
For the proof of Theorem <ref>, we need to combine the approximation algorithm with 
novel insights concerning the “decomposability” of schedules along small separators in order to design a treewidth-based dynamic programming algorithm for the problem. A brief summary of the ideas used in this proof is provided at the beginning of Section <ref>.
 

We complement our positive results which use k as a parameter with an algorithmic lower bound showing that Coordinated Motion Planning is [1]-hard (and hence not fixed-parameter tractable under well-established complexity-theoretic assumptions) when parameterized by the energy budget ℓ. This result (Theorem <ref> below) contrasts the fixed-parameter tractability of the problem under the same parameterization when restricted to solid grids <cit.>. 


theoremwone

  is [1]-hard when parameterized by ℓ.


While Theorem <ref> establishes the intractability of the problem when parameterized by the energy on general graphs, one can in fact show that  is fixed-parameter tractable under the same parameterization when the graphs are “well-structured” in the sense of having bounded local treewidth <cit.>. This implies fixed-parameter tractability, e.g., on graphs of bounded genus and generalizes the aforementioned result on grids <cit.>.

theoremfptenergy

	 is  parameterized by ℓ on graph classes of bounded local treewidth.





 
         
    

 
 
 
 
 
 


    Further Related Work.


        As surveyed above, the computational complexity of has received significant attention, particularly by researchers in the fields of computational geometry, AI/Robotics, and theoretical computer science. The problem has been shown to remain -hard under a broad set of restrictions, including on graphs where only a single vertex is not occupied <cit.>, on grids <cit.>, and bounded-height subgrids <cit.>. On the other hand, a feasibility check for the existence of a schedule can be carried out in polynomial time <cit.>. The recent AAMAS blue sky paper <cit.> also highlighted the need of understanding the hardness of the problem and asked for a deeper investigation of its parameterized complexity. 
 
  
    


§ TERMINOLOGY AND PROBLEM DEFINITION

The graphs considered in this paper are undirected simple graphs. We assume familiarity with the standard graph-theoretic concepts and terminology <cit.>. For a subgraph H of a graph G and two vertices u, v ∈ V(H), we denote by _H(u, v) the length of a shortest path in H between u and v. We write [n], where n ∈, for {1, …, n}.


We also assume basic familiarity with parameterized complexity theory, including fixed-parameter tractability, parameterized reductions, and the class [1]
 <cit.>. 


    Parameterized Complexity.

 A parameterized problem Q is a subset of Ω^* ×, where Ω is a fixed alphabet. Each instance of Q is a pair (I, κ), where κ∈ is called the parameter. A parameterized problem Q is
fixed-parameter tractable () <cit.>, if there is an
algorithm, called an -algorithm,  that decides whether an input (I, κ)
is a member of Q in time f(κ) · |I|^(1), where f is a computable function and |I| is the input instance size.  The class  denotes the class of all fixed-parameter tractable parameterized problems.

Showing that a parameterized problem is hard for the complexity classes [1] or [2] rules out the existence of a fixed-parameter algorithm under well-established complexity-theoretic assumptions. Such hardness results are typically established via a parameterized reduction, which is an analogue of a classical polynomial-time reduction with two notable distinctions: a parameterized reduction can run in time f(k)· n^(1), but the parameter of the produced instance must be upper-bounded by a function of the parameter in the original instance. We  refer to <cit.> for more information on parameterized complexity. 


 


    Treewidth.

Treewidth is a structural parameter that provides a way of expressing the resemblance of a graph to a forest. 
 Formally, the treewidth of a graph is defined via the notion of tree decompositions as follows.

[Tree decomposition]
A tree decomposition of a graph G is a pair (T,β) of a tree T and β: V(T) → 2^V(G),
such that: 


  * ⋃_t ∈ V(T)β(t) = V(G), 

  * for any edge e ∈ E(G), there exists a node t ∈ V(T) such that both endpoints of e belong to β(t), and

  * for any vertex v ∈ V(G), the subgraph of T induced by the set T_v = {t∈ V(T): v∈β(t)} is a tree.

The width of (T,β) is max_v∈ V(T){|β(v)|}-1. The treewidth of G is the minimum width of a tree decomposition of G.



Let (T,β) be a tree decomposition of a graph G. We refer to the vertices of the tree T as nodes. We always assume that T is a rooted tree and hence, we have a natural parent-child and ancestor-descendant relationship among nodes in T. A leaf node nor a leaf of T is a node  with degree exactly one in T which is different from the root node. All the nodes of T which are neither the root node or a leaf are called non-leaf nodes. 
The set β(t) is called the bag at t.
  For two nodes u,t ∈  T, we say that u is a descendant of t, denoted u ≼ t, if t lies on the unique path connecting u to the root. Note that every node is its own descendant. If u≼ t and u≠ t, then we write u≺ t.
 For a tree decomposition (T,β) we also have a mapping γ:V(T)→ 2^V(G) defined as γ(t)=⋃_u≼ tβ(u).  


 
 
  We use the following structured tree decomposition in our algorithm. 
  
[Nice tree decomposition]Let (T,β) be a tree decomposition of a graph G, where r is the root of T. The tree decomposition (T,β) is called a nice tree decomposition if the following conditions are satisfied. 
 
 
  * β(r) =∅ and β(ℓ) =∅ for every leaf node ℓ of T; and
 
  * every non-leaf node (including the root node) t of T is of one of the following types:
 
 
  * Introduce node: The node t has exactly one child t' in T and β(t)=β(t') ∪{v}, where v ∉β(t').
  
  * Forget node: The node t has exactly one child t' in T and β(t)=β(t') ∖{v}, where v ∈β(t').
  
  * Join node: The node t has exactly two children t_1 and t_2 in T and β(t)=β(t_1) =β(t_2).
 
 
 


A graph class closed under vertex and edge deletion is said to have bounded local treewidth <cit.> if the treewidth of each graph in the class is upper-bounded by a function of its diameter. Examples of classes of bounded local treewidth include, e.g., graphs of bounded genus <cit.>.


Efficient fixed-parameter algorithms are known for computing a nice tree-decomposition of near-optimal width:

[<cit.>] 
	There exists an algorithm which, given an n-vertex graph G and an integer k, in time 2^(k)· n either outputs a nice tree-decomposition of G of width at most 2k+1 and (n) nodes, or determines that (G)>k.
  

Boundaried graphs. Roughly speaking, a boundaried graph is a graph where some vertices are annotated. A formal definition is as follows. 

[Boundaried Graph]
A boundaried graph is a graph G with a set X⊆ V(G) of distinguished vertices called boundary vertices. The set X is the boundary of G. A boundaried graph (G,X)  is called  a p-boundaried graph if |X|≤ p.




A p-boundaried subgraph of  a graph G is a p-boundaried graph (H,Z) such that (i) H is a vertex-induced subgraph of G and Z separates V(H)∖ Z from V(G)∖ V(H).  

 
 
 
 Let G be a graph with a tree decomposition (T,β) and let x∈ V(T).  
 
  * G_x,T^↑ denotes the boundaried graph obtained by taking the subgraph of G induced by the set V(G)∖  (γ(x)∖β(x)), with β(x) as the boundary. 

  * Similarly, 
G_x,T^↓ denotes the boundaried graph obtained by taking the subgraph of G induced by γ(x) with β(x) as the boundary.
  
 



Notice that if G is a graph with a tree decomposition (T,β) of width at most k and x∈ T, then G_x^↑ and G_x^↓ are both (k+1)-boundaried graphs.





    Problem Definition.

In our problems of interest, we are given an undirected graph G and a set ={R_1, R_2, …, R_k} of k robots where  is partitioned into two sets  and . Each R_i ∈ has a starting vertex s_i and a destination vertex t_i in V(G) and each R_i ∈ is associated only with a starting vertex s_i ∈ V(G).
We refer to the elements in the set {s_i| i∈ [k]}∪{t_i| R_i∈} as terminals. The set  contains robots that have specific destinations they must reach, whereas  is the set of remaining “free” robots. We assume that all the s_i are pairwise distinct and that all the t_i are pairwise distinct.  At each time step, a robot may either move to an adjacent vertex, or stay at its current vertex, and robots may move simultaneously.  We use a discrete time frame [0, t], t ∈, to reference the sequence of moves of the robots and in each time step x ∈ [0, t] every robot remains stationary or moves.
 
 
A route for robot R_i is a tuple W_i=(u_0, …, u_t) of vertices in G such that (i) u_0=s_i and u_t=t_i if R_i ∈ and (ii) ∀ j ∈ [t], either u_j-1 =u_j or u_j-1u_j∈ E(G).
         Put simply, W_i corresponds to a “walk” in G, with the exception that consecutive vertices in W_i may be identical (representing waiting time steps), in which R_i begins at its starting vertex at time step 0, and if R_i ∈ then R_i reaches its destination vertex at time step t. Two routes W_i=(u_0, …, u_t) and W_j=(v_0, …, v_t), where i ≠ j ∈ [k], are non-conflicting if (i) ∀ r ∈{0, …, t}, u_r ≠ v_r, and (ii) ∄ r ∈{0, …, t-1} such that v_r+1 =u_r and u_r+1 =v_r. Otherwise, we say that W_i and W_j conflict. Intuitively, two routes conflict if the corresponding robots are at the same vertex at the end of a time step, or go through the same edge (in opposite directions) during the same time step. 

A schedule  for  is a set of pairwise non-conflicting routes W_i, i ∈ [k], during a time interval [0, t].  The (traveled) length of a route (or its associated robot) within  is the number of time steps j such that u_j≠ u_j+1. The total traveled length of a schedule is the sum of the lengths of its routes; this value is often called the energy in the literature (e.g., see <cit.>).

 
Using the introduced terminology, we formalize the Generalized Coordinated Motion Planning with Energy Minimization () problem below.  

[] 
    A tuple (G, =(,), k, ℓ), where G is a graph, ={R_i | i ∈ [k]} is a set of robots partitioned into sets M and F, where each robot in M is given as a pair of vertices (s_i, t_i)  and each robot in F as a single vertex s_i, and k, ℓ∈.

     Is there a schedule for  of total traveled length at most ℓ?


 
  
By observing that the feasibility check of Yu and Rus <cit.> transfers seamlessly to the case where some robots do not have destinations, we obtain the following.



    The existence of a schedule for an instance of  can be decided in linear time. Moreover, if such a schedule exists, then a schedule with total length traveled of (|V(G)|^3) can be computed in (|V(G)|^3) time. 
 

Proposition <ref> implies inclusion in , and allows us to assume henceforth that every instance of  is feasible (otherwise, in linear time we can reject the instance). 
     We denote by  the restriction of  to instances where ||=1.
 We remark that even though is stated as as a decision problem, all the algorithms provided in this paper are constructive and can output a corresponding schedule (when it exists) as a witness.
 



§ AN ADDITIVE  APPROXIMATION FOR 


In this section, we give an  approximation algorithm for  with an additive error that is a function of the number k of robots. 

 
We start by providing a high-level, low-rigor intuition for the main result of this section. Let =(G, =(,), k, ℓ) be an instance of . Ideally, we would like to route the robots in  along shortest paths to their destinations, while having the other robots move away only a “little” (ϵ(k)-many steps) to unblock the shortest paths for the robots in . Unfortunately, this might not be possible as it is easy to observe that a free robot might have to travel a long distance in order to unblock the shortest paths of other robots. (For instance, think about the situation where a free robot is positioned in the middle of a long path of degree-2 vertices that the shortest paths traverse.) However, we will show that such a situation could only happen if the blocking robots are positioned in simple graph structures containing a long path of degree-2 vertices. 

We then exploit these simple structures to “guess” in -time, for each robot, a location which it visits in an optimal solution and which is in the vicinity of a safe location, called a “haven”; this haven is centered around a “nice” vertex of degree at least 3, and allows the robot to avoid any passing robot within ϵ(k) moves. We show how to navigate the robots to these havens optimally in the case of , and with an ϵ(k) overhead in the case of . Moreover, this navigation is well-structured and can be leveraged to show that no robot in an optimal solution will visit the same vertex many times. 
A similar navigation takes place at the end, during the routing of the robots from their havens to their destinations.

Once
we obtain such a reduced instance in which all starting positions and destinations of the
 robots are in havens, we can use our intended strategy to navigate each robot in  along a shortest path,
 with only an ϵ(k) overhead, which immediately gives us the approximation result and the property that no robot visits any vertex more than ϵ(k) times in an optimal solution. 
This latter property about the optimal solution is crucial, as we exploit it later in Section <ref> to design an intricate dynamic programming algorithm over a tree decomposition of the input graph.

In addition, each free robot moves at most ϵ(k) times in the considered solution for the reduced instance.
This, together with the equivalence between  and the reduced instance in the case of ,  allow us to restrict the movement of the free robots in an optimal solution to only ϵ(k)-many locations, which we use in Section <ref> to obtain the  algorithm for .




 We start by defining the notion of a nice vertex and its haven. 
  
[Nice Vertex]

  A vertex w∈ V(G) is nice if there exist three connected subgraphs C_1, C_2, C_3 of G such that: (i) the pairwise intersection of the vertex sets of any pair of these subgraphs is exactly w, and (ii) |V(C_1)| ≥ k+1, |V(C_2)| ≥ k+1, and |V(C_3)| ≥ 2. If w is nice, let x ∈ V(C_3) be a neighbor of w, and define the haven H_w of w to be the subgraph  of G induced by the vertices in {x}∪ V(C_1) ∪ V(C_2) whose distance from w in H_w (i.e., _H_v(w, u), for u ∈ V(C_1) ∪ V(C_2)) is at most k. 


 

For a set S ⊆ of robots and a subgraph H, a configuration of S w.r.t. H is an injection ι:   S ⟶ V(H). The following lemma shows that we can take the robots in a haven from any configuration to any other configuration in the haven, while incurring a total of (k^3) travel (in the haven) length.



 


Let w be a nice vertex, let C_1, C_2, C_3 be three subgraphs satisfying conditions (i) and (ii) of Definition <ref>, and let H_w be a haven for w. 
Then for any set of robots S ⊆ in H_w with current configuration ι(S), any configuration ι'(S) with respect to H_w can be obtained from ι(S) via a sequence of (k^3) moves that take place in H_w.



Let T_1 (resp. T_2) be a Breadth-First Search (BFS) tree in H_w rooted at w whose vertex set is V(H_w) ∩ V(C_1) (resp. V(H_w) ∩ V(C_2)). Note that T_1 and T_2 are well defined since C_1 and C_2 are connected. Moreover, we have |V(T_1)|, |V(T_2)| ≥ k+1, and w is the only intersection between the two sets V(T_1) and V(T_2). Let x ∈ H_w be the neighbor of w in C_3. To arrive at configuration ι'(S) from ι(S), we perform the following process.

In the first phase of this process, we move all the robots in S from their current vertices to arbitrary distinct vertices in V(T_1) - {w}. Note that this is possible since |V(T_1) - {w}| ≥ k. Moreover, this is achievable in (k^2) robot moves since every vertex in S is at distance at most k from w. For instance, one way of achieving the above is to move first the robots in S that are in T_1, one by one to the deepest unoccupied vertex in T_1, then repeat this for the robots in S that are in T_2, and finally move the robot on x (if there is such a robot) to T_1. 

Let S_2= {R ∈ S |ι'(R) ∈ V(T_2)∖{w}} (i.e., the set of robots in S whose final destinations w.r.t. ι'(S) are in T_2 excluding vertex w). In the second phase, we route the robots in S_2 in reverse order of the depths of their destinations in T_2; that is, for two robots R and R' in S_2, if R's destination is deeper than that of R', then R is routed first; ties are broken arbitrarily. To route a robot R ∈ S_2, we first move R in T_1 towards w as follows. Let P be the unique path in T_1 from w to the vertex at which R currently is. (Note that P may contain other robots.) We “pull” the robots along P towards w, and into T_2 until R reaches w, and then move R to vertex x. When a robot R'≠ R on P reaches w, R' is then routed towards an unoccupied vertex in T_2 by finding a root-leaf path P' in T_2 that contains an unoccupied vertex (which must exist since |V(T_2)| ≥ k+1), and “pushing” the robots on P' down that path, possibly pushing (other) robots on P' along the way, until R' and every robot on P' occupy distinct vertices in T_2. Once R is moved to x, all the robots on P that were moved into T_2 during this step are moved back into T_1 (i.e., we reverse the process). Afterwards, R is routed to its destination in T_2, along the unique path from w to that destination; note that this path must be devoid of robots due to the ordering imposed on the robots in the routing scheme.  The above process is then repeated for every robot in S_2, routing it to its location stipulated by ι'(S). 

In the last phase, we move all the robots in S_1=S-S_2, one by one, to T_2  by applying the same “sliding” operation as in the second phase. As a robot is moved to T_2, it may push the robots in T_2 deeper into T_2. Note that, during this process, no robot in T_2 occupies a vertex that is an ancestor of a robot S_1, and hence no robot in T_2 “blocks” a robot in S_1 from coming back to T_1. We then route the robots in S_1 from T_2 back into T_1 in the reverse order of the depths of their destinations w.r.t. ι'(S) in T_1. However, if a robot has either w or x as a destination, then we route the robot whose destination is w last, and the one whose destination is x second from last.
To route a robot R∈ S_1 from T_2 to its destination in T_1, we pull R up in T_2 towards w, possibly pulling along the way other robots (that are only in S_1) into T_1,
until R escapes to x. We then slide the robots that we pulled into T_1 back to T_2 and route R to its final destination in T_1 ∪{w, x}. We repeat this step until all the robots in S_1 have been routed to their destination in T_1 ∪{w, x} as stipulated by ι'(S). 

    Since |V(H)| = (k), it is not difficult to verify that the total traveled length by all the robots over the whole process is (k^3).  
 


 
 
Let w be a vertex of degree at least 3 that is contained in a (simple) cycle C of length at least 2k+2. Then w is nice.


 
Let C=(w_0=w, w_1, …, w_r), where r ≥ 2k+1.
Let x ∉{w_1, w_r} be a neighbor of w. If x ∉ V(C), then the subgraphs consisting of the single edge wx, and the two subpaths (w, w_1, …, w_k) and (w, w_r, …, w_r-k+1) of C satisfy conditions (i) and (ii) in Definition <ref>, and w is nice. 

Suppose now that x ∈ V(C), and let x_1, x_2 be the neighbors of x that appear adjacently (on either side) to x on C.
Let P_wx_1 be the subpath of C between w and x_1 and P_wx_2 that between w and x_2. At least one of P_wx_1, P_wx_2 contains at least k+1 vertices; otherwise, C would have length at most 2k. Assume, without loss of generality, that P_wx_1 contains at least k+1 vertices, and let P_w^- be the subpath of P_wx_1 that starts at w and that contains exactly k+1 vertices. Assume, without loss of generality, that w_1 is on P_w^-, and hence w_k is the endpoint of P_w^- other than w. Then it is easy to see that the three subgraphs consisting of the edge ww_r, the path P_w^-, and the connected subgraph consisting of wx +P_w_r-1w_k, where P_w_r-1w_k is the subpath of C between w_r-1 and w_k, satisfy conditions (i) and (ii) in Definition <ref>, implying that w is nice. 
 

 


Call a path P in G a 2-path if P is an induced path of degree-2 vertices in G. The next lemma is used to characterize the possible graph structures around a vertex that is not nice; an illustration for the four cases handled by the lemma is provided in Figure <ref>. 
 


For every vertex v that is not nice, one of the following holds:


    
  (1) There is a nice vertex at distance at most 3k from v; or
    
    
  (2) vertex v is on a 2-path whose both endpoints are nice vertices; or 
    
  (3) there is a 2-path P 
         such that one of its endpoints is nice and the other is contained in a connected subgraph Q of size at most 8k that P cuts from the nice vertex and such that v is in P ∪ Q; or 
        
  (4) Either |V(G)| ≤ 8k, or G consists of a 2-path P, each of whose endpoints is contained in a subgraph of size at most 8k, such that P cuts the two subgraphs from one another.  
  

 

Suppose that v is not a nice vertex, and assume that (1) does not hold (i.e., that there is no nice vertex at distance at most 3k from v). We will show that one of the Statements (2)-(4) must hold.

Let T be a BFS-tree of G rooted at v. For a vertex x in T, denote by deg_T(x) the degree of x in T, by T_x the subtree of T rooted at x, and let T_x^-= T - V(T_x). For two vertices x, y ∈ T, denote by P_xy the unique path between x and y in T, and by d_T(x, y) the distance between x and y in T, which is |P_xy|. 

 If there is no vertex x in T with deg_T(x) ≥ 3, then T is a path of vertices, each of degree at most 2 in T.  Note that any edge in G is between two vertices that are at most one level apart in the BFS-tree T. If there is an edge xy in E(G)-E(T) that is between two vertices that are not at the same level of T, then assume w.l.o.g. that x has a higher level than y. We can “re-graft” y so that  x becomes its parent in T (i.e., cut y from its current parent and attach it to x) to obtain another BFS-tree rooted at v and containing a vertex x with deg_T(x) ≥ 3. Suppose now that all the edges in E(G)-E(T) join vertices at the same level of T. Let x and y be the two vertices in T of degree-3 in G that are of minimum distance to v, and note that xy ∈ E(G). Moreover, P_xy-x - y is a 2-path in G. If both x and y are nice, then v is contained in an induced path of degree-2 vertices in G that has two nice vertices at both ends (since no edges can exist between any two vertices along that path), and hence, v satisfies Statement (2) of the lemma. If one of x, y, say x is nice, then y must be nice as well by Lemma <ref>, since d_T(v, x) =d_T(v, y) > 3k (as (1) does not hold), and hence y is a degree-3 vertex that is contained in the cycle P_xy +xy of length at least 3k+1. Suppose now that both x and y are not nice. Observe in this case that d_T(v,x)=d_T(v, y) ≤ k+1; otherwise, x and y would be nice by Lemma <ref>. If each of T_x, T_y contains more than k+1 vertices, then again x and y would be nice. It follows that at least one of T_x, T_y, say T_x, contains at most k vertices, and hence G consists of a subgraph containing T_x, P_xy and at most k neighbors in T_y of the vertices in T_x that must be within distance k from y, followed by a 2-path (the rest of T_y) in G. Therefore, G consists of a subgraph of at most 4k+2 vertices plus a 2-path in G, and Statement (4) in the lemma is satisfied. 

Therefore, we may assume henceforth that there is a vertex x in T satisfying deg_T(x) ≥ 3.

We first claim that any subtree of T that contains a vertex of degree at least 3 in T contains a vertex x satisfying deg_T(x) ≥ 3 and |V(T_x^-)| ≥ 3k, otherwise the statement of the lemma is satisfied.


Let T_v' be a subtree containing a vertex whose degree in T is at least 3, and suppose that there is no vertex x ∈ T_v' satisfying deg_T(x) ≥ 3 and |V(T_x^-)| ≥ 3k. Since there exists a vertex in T_v' whose degree in T is at least 3, for any vertex x in T_v' satisfying deg_T(x) ≥ 3, we have |V(T_x^-)| < 3k. Let x be a vertex in T_v' satisfying deg_T(x) ≥ 3 and with the maximum d_T(v, x). Since |V(T_x^-)| < 3k and T_x^- is connected and contains v, it follows that d_T(v, x) < 3k, and hence d_G(v, x) < 3k. Since – by our assumption – (1) is not satisfied, there is no nice vertex within distance at most 3k from v, it follows that x is not nice. Moreover, by the choice of x, for every child y of x in T, T_y is a path of degree-2 (in T) vertices. Since x is not nice, at most one of the paths rooted at a child of x can contain more than k vertices; call such a path long. If no such long path exists, then T_x contains at most 4k vertices; otherwise, we can split T_x into two subgraphs C_2, C_3, intersecting only at x and each containing at least k+1 vertices. It follows in this case that the number of vertices in T, and hence in G, is |V(T_x)| + |V(T_x^-)| ≤ 7k, and G satisfies Statement (4) of the lemma (with the 2-path being empty). Suppose now that a long path P_x of degree-2 vertices rooted at x exists. Then since x is not nice, T_x - V(P_x) contains at most k vertices, and hence T can be decomposed into two parts P_x and T-P_x that intersect only at x, where |V(T-P_x)| ≤ 4k. Note that, by the property of a BFS-tree, no vertex on P_x at distance more than 3k from x can be a neighbor of a vertex in V(T-P_x), and hence, any vertex on P_x of distance at least 3k from x is a cut-vertex that cuts G into a connected subgraph of size at most 7k plus a 2-path in G, thus satisfying the Statement (4) of the lemma. 

Suppose now that any subtree of T that contains a vertex of degree at least 3 in T contains a vertex x satisfying deg_T(x) ≥ 3 and |V(T_x^-)| ≥ 3k. Since there exists a vertex x satisfying deg_T(x) ≥ 3, let w be such a vertex satisfying |V(T_w^-)| ≥ 3k and such that no ancestor y of w in T satisfies deg_T(y) ≥ 3 and |V(T_y^-)| ≥ 3k.

If w is nice, 
consider the path P_wv of T. If there exists an internal degree-3 vertex (in T) on P_wv, then let x be the farthest such vertex from v (i.e., closest such ancestor of w) on this path. By the choice of w, |V(T_x^-)| < 3k, and hence v ∈ V(T_x^-) is contained in a subgraph of size at most 3k that is connected by a (possibly empty) path of vertices of degree 2 in T to w. Since w is nice and Statement (1) is not satisfied (by our assumption), we have d_T(v, w) > 3k. Since |V(T_x^-)| < 3k, by the properties of BFS-trees, no vertex in V(T_x^-) could be adjacent in G to any vertex in T_w or to any vertex y on P_xw, the path of T between x and w, satisfying 
d_T(v, y) > 3k. Therefore, by picking any vertex u on P_xw whose distance from w is at most 1 (Which must exist), we have a cut-vertex in G that cuts G into a component of size at most 6k containing v, connected by a 2-path in G to a nice vertex w, as stated in Statement (3) of the lemma. 

Suppose now that no vertex x satisfying deg_T(x) ≥ 3 exists along P_vw. 
Note that |P_vw| > 3k,  since the distance between v and the nice vertex w is more than 3k. 

If deg_T(v) ≥ 3, then since v is not nice, it follows that the union of all the subtrees rooted at the children of v, except the subtree containing w, is at most 2k, and hence, by a similar analysis to the above, it is easy to see that v is part of a connected subgraph of size at most 4k that is connected by a 2-path P (which is a subpath of P_vw) in G to a nice vertex w such that P cuts this subgraph from w, thus satisfying Statement (3) of the lemma. 

Suppose now that deg_T(v) is 2, and hence deg_G(v)=2. Let w' be the child of v such that T_w' contains w and v' be the other child of v (i.e, such that T_v' does not contain w ). 
 

Let z be the first descendant of v in T_v' such that deg_G(z) ≥ 3; if no such z exists, then v must be on a 2-path in G that ends a nice vertex w, thus satisfying Statement (3) of the lemma.

Suppose now that z exists. If z is nice, then d_T(v, z) > 3k. Observe that any neighbor of z in G must be within 1 level from that of z in T. Observe also that Since P_vz is an induced path of degree-2 vertices in G. If z has a neighbor x in G on P_vw, let x be the neighbor with the minimum d_T(v, x). Then x must be nice since x is a degree-3 vertex on a cycle of length at least 2k+2 (see Lemma <ref>). Moreover, by the choice of z and x, v is contained in an induced path of degree-2 vertices in G whose both endpoints are nice vertices (x and z), thus satisfying Statement (2) of the lemma. Similarly, if any vertex x on P_vw has a neighbor in G, which must be a vertex below z in T_v', and hence x must be on a cycle of length at least 2k+2 and must be nice, and v satisfies Statement (2) of the lemma. Otherwise, v is contained in a 2-path in G that ends at nice vertices, namely z and w, again satisfying Statement (2) of the lemma.

Suppose now that z is not nice. Since the length of P_zv+P_vw is more than 3k and z is not nice, the number of vertices in T_z is at most 2k. Note that, since z is not nice, z cannot be contained in a cycle of length more that 2k+1, and hence, no edge in G exists between a vertex in T_w and a vertex in T_z. If no vertex in P_vw has a neighbor in T_v' then v is contained in 2-path P that on one side ends with a nice vertex w, and on the other side with a connected subgraph T_z of size at most 2k such that P cuts T_z from w, thus satisfying Statement (3) of the lemma. Otherwise, any vertex x on P_vw with a neighbor in T_z must be within distance at most k+1 from v (otherwise, z would be contained in a cycle of length at least 2k+2 and would be nice). It follows that v is contained in a connected subgraph of size at most 4k+2 that is connected by a 2-path P in G to a nice vertex w such that P cuts w from this subgraph containing v, and thus satisfying Statement (3) of the lemma.
  
Suppose now that w is not nice. Then since |V(T_w^-)| ≥ 3k by the choice of w, |V(T_w)| ≤ 2k. 

Consider the path P_wv of T. If there exists a degree-3 (in T) vertex on P_wv, then let x be the deepest such vertex (ancestor of w) on this path. By the choice of w, |V(T_x^-)| < 3k, and hence v ∈ V(T_x^-) is contained in a subgraph of size at most 3k. Observe that any vertex in V(T_x^-) cannot have a neighbor on P_xw that is at distance more than 3k from x. Hence, either the total size of G is at most 8k (if a vertex in V(T_x^-) has a neighbor in T_w), or G can be decomposed into a 2-path P, each of its endpoints is a contained in a connected subgraph of size at most 8k (one of the two subgraphs must contain v) such that P separates the two. In either of the two cases, v satisfies Statement (4) of the lemma.

Suppose now that no such x exists, then w is connected to v by a path of degree-2 vertices in T. By symmetry, we can assume that, for every child v' of v, either T_v' does not contain a vertex x satisfying deg_T(x) ≥ 3, or contains a vertex w' that is not nice and satisfying |V(T_w')| ≤ 2k, |V(T_w'^-)| ≥ 3k, and is connected to v via a path of degree-2 vertices in T. 

If deg_T(v) ≤ 2, then we can argue – similarly to the above – that v must satisfy the lemma. We summarize these arguments below for the sake of completeness. Let w' be the child of v such that T_w' contains w and v' be the other child of v. Either T_v' is a path of vertices, each of degree at most 2 in T, or there exists a vertex x in T_v' such that  deg_T(x) ≥ 3,  x is not nice, x satisfies |V(T_x)| ≤ 2k and |V(T_x^-)| ≥ 3k, and P_xv is a path of degree-2 vertices in T. If |P_vw| ≤ 2k, then |V(T_w')| ≤ 4k and no vertex in T_w' can be adjacent in G to any vertex in T_v' whose depth in T is more than 4k; it is easy to see in this case that Statement (4) of the lemma holds. Suppose now that |P_vw| > 2k and observe that since w is not nice, no vertex in T_w can be adjacent to a vertex in T_v'; otherwise, w would be contained in a cycle of length at least 2k+2. Therefore, the only edges in G that could exist between T_w' and T_v' are edges between P_vw and T_v'. If no edge exists between T_w' and T_v', then Statement (4) of the lemma holds. Otherwise, let xy be the edge between a vertex x in P_vw and a vertex y in Tv such that x is of minimum depth in T_w'. If x is nice then y must be nice (since both would be contained in a cycle of length at least 2k+2) and Statement (2) of the lemma holds. Suppose now that both x and y are not nice, which implies that each has depth at most k+1 in T. Moreover, either T_x or T_y must contain at most k vertices. In each of these two cases, it is easy to see that Statement (4) of the lemma holds.



Suppose now that v has at least three children in T. At most one of these children can satisfy that the subtree of T rooted at it has at least k vertices; otherwise, v would be nice. If no child v_i of v satisfies that |V(T_v_i)| ≥ k, then it is easy to see that |V(G)| ≤ 6k, and hence Statement (4) of the lemma is satisfied, as otherwise v would be nice. Suppose now that exactly one child of v, say v_1, is such that |V(T_v_1)| ≥ k, and note in this case that |V(T) -V(T_v_1)| ≤ 2k. If T_v_1 contains a vertex x     satisfying deg_T(x) ≥ 3, then T_v_1 contains a vertex w that is not nice and satisfying |V(T_w)| ≤ 2k, |V(T_w^-)| ≥ 3k, and such that P_vw is a path of degree-2 vertices in T. Since |V(T) -V(T_v_1)| ≤ 2k, and hence, any vertex in 
V(T) -V(T_v_1) can be adjacent only to vertices on P that are within distance at most 2k from v (since T is a BFS-tree), either G has at most 6k vertices, or it consists of two connected subgraphs, each of size at most 4k that are connected by a 2-path of G (which is a subpath of P) that separates the two subgraphs, and Statement (4) of the lemma holds. Suppose now that T_v_1 consists of a path P of vertices each of degree at most 2 in T. Again, by the properties of the BFS-tree T, any vertex in V(T) -V(T_v_1) can be adjacent to vertices on P that are within distance at most 2k from v. It follows in this case that G can be decomposed into a connected subgraph of size at most 4k that contains v and that is connected by a 2-path, and Statement (4) of the lemma holds.
 


[Vertex Types]

Let v be a vertex in G that is not nice. We say that v is a type-(i) vertex, where i ∈{1, …, 4}, if v satisfies Statement (i) in Lemma <ref> but does not satisfy any Statement (j), where j < i (if Statement (j) exists). Note that, by Lemma <ref>, every vertex v that is not nice must be a type-(i) vertex for some  i ∈{1, …, 4}. 


The following lemma shows that we can restrict our attention to the case where there is no type-(4) vertex in G.



Let =(G, =(, ), k, ℓ) be an instance of . If there exists a type-(4) vertex v ∈ V(G) then  can be solved in time ^*((4k^2+16k)^2k) and hence is .




Suppose that there exists a type-(4) vertex v ∈ V(G). Then G can be decomposed into two connected subgraphs, H_1, H_2, that are connected by a 2-path P in G. We will show that in this case   can be solved in -time.

Call a vertex x ∈ V(G) critical if _G(x, w) ≤ k for some w∈ V(H_1) ∪ V(H_2) ∪{s_i, t_i| R_i∈}. That is, x is critical if it is within distance at most k from a vertex in one of the two subgraphs H_1, H_2, or if it is within distance at most k from the starting position or the ending position of some robot.

Initially, all robots are located at critical vertices (since their starting vertices are critical). It is not difficult to prove, by induction on the number of moves and by normalizing the moves in a solution, that there exists an optimal solution to  in which 
if a robot R∈ is not a critical vertex, then it is moving directly without stopping or changing direction on P between two critical vertices.

 

Define a configuration to be an injection from  into the set of critical vertices in G. Define the configuration graph C_G to be the weighted directed graph whose vertex-set is the set of all configurations, and whose edges are defined as follows. There is an edge from a configuration q to a configuration q' if and only 
q' can be obtained from q via a single (parallel) move of a subset of the robots, or q and q' are identical with the exception of a single robot's transition from a critical vertex on P to another critical vertex on P along an unoccupied path; in either case, the weight of edge (q, q') is the total traveled length by all the robots for the corresponding move/transition.

To decide , we compute the shortest paths (e.g., using Dijkstra's algorithm) between the initial configuration, defined based on the input instance (in which every robot is at its initial position), and every configuration in the configuration graph in which the robots in  are located at their destinations, and then choose a shortest path, among the computed ones, with total length at most ℓ if any exists. 

 The number of critical vertices is at most 2k· 2|| + |V(H_1)|+|V(H_2)| ≤ 4k^2 + 16k, and hence the number of configurations is at most (4k^2+16k)^k.  It follows that the problem can be solved in ^*((4k^2+16k)^2k) time, and hence is .    
 


 

Let =(G, =(, ), k, ℓ) be an instance of , and let opt() be an optimal solution for .
Let v be a type-(3) vertex, and let Q be the connected subgraph of size at most 8k that is connected by a 2-path P to a nice vertex n_R, and such that v ∈ V(Q) ∪ V(P). If a robot R∈ starts on v, then the route of R in opt() cannot visit n_R and then visit a vertex in V(Q).




Let R_1 ≠ R be the single robot in . Observe that
the only reason for R to visit n_R is to reverse order with R_1 whose destination must be in this case in V(P) ∪ V(Q). (Otherwise, R would never have to leave P ∪ Q.) But then R_1 must enter P ∪ Q for the last time before R does, and hence R will never end up in a vertex in Q in opt() since |P| ≥ 3k. 
 
 


Let =(G, =(, ), k, ℓ) be an instance of , and let opt() be an optimal solution for .
Let v be a type-(3) vertex, and let Q be the connected subgraph of size at most 8k that is connected by a 2-path P of length at least k+1 to a nice vertex n_R, and such that v ∈ V(Q) ∪ V(P). If a robot R∈ starts on v, then the route of R in opt() cannot visit a vertex in V(Q) and then visit n_R.


  
Let R_1 ≠ R be the single robot in . The robot R might visit Q because it is pushed inside by R_1 or by some other robot R'∈. If it is pushed by R_1 to change their order in Q, then it would  never need to go as far as n_R (since |P| ≥ k+1) after visiting Q to make space for R_1. On the other hand, if it is pushed by another robot R', then since neither of the two has a destination, we can exchange R and R' ∈, and change the schedule to a shorter one in which R' goes to n_R and R ends up in Q instead.
  


 
 
Let =(G, =(,), k, ℓ) be an instance of , v a nice vertex, H_v a haven for v, and S a schedule for . There is a polynomial time algorithm that takes S and computes a schedule S' such that:

    
  * each robot R_i∈ 
         enters H_v at most once and leaves H_v at most once; moreover, if R_i starts in H_v, then it will never re-enter H_v if it leaves it;
    
  * the total traveled length of all the robots outside of H_v in S' is upper-bounded by the total traveled length of all the robots outside of H_v in S; and
    
  * the total traveled length of all the robots inside of H_v in S' is (k^4). 





We will construct the schedule S' as follows. 
For every robot R_i∈, define v^i_first and v^i_last as the first and last vertex, respectively, that R_i visits in H_v. 
Let W_i be the route for R_i in S. 
We let its route W_i' in S' follow W_i until it reaches the vertex v^i_first for the first time, with a slight modification that we might “freeze” R_i at its place for several time-steps when some other robot is either about to enter H_v or is leaving H_v. 
In addition, when R_i enters H_v in v^i_first, we change its routing in a way that it stays in H_v until it is its time to leave from v^i_last and never returns to H_v again. 
That is, when a robot R_i is about to enter v^i_first, we “freeze” the execution of the schedule and reconfigure the robots currently in H_v so that v^i_first is empty, for example by using Lemma <ref>, and then move R_i to v^i_first. 
From now on, we keep R_i in H_v, possibly moving it around each time we “freeze” the execution of the schedule to let a robot enter H_v or leave H_v. 
When all the robots are either in H_v or on the positions where they are at the time when R_i moves from v^i_last to some neighbor of v^i_last and never returns to H_v afterwards, we “freeze” the execution of the schedule and we reconfigure H_v to a configuration where R_i is at v^i_last by using Lemma <ref>. 
From this position R_i again follows W_i. 
It is easy to see that the total traveled length of S' outside of H_v is at most the total traveled length of S outside of H_v, as each robot is taking exactly the same steps until it reaches H_v for the first time, then it stays in H_v and after it leaves H_v, it is repeating the same steps as it does in S after leaving H_v for the last time. 
In addition, all the robot movements inside of H_v took place only when we froze the execution of the schedule to either let a robot enter H_v or leave H_v. This happens at most 2k times and each reconfiguration takes (k^3) steps by Lemma <ref>.
Hence the total traveled length of S' inside of H_v is at most (k^4).
Since we also modified the solution such that every robot enters and leaves H_v in S' at most once, the lemma follows.[With a more careful analysis, it is possible to show that we only need at most k steps to enter H_v and at most (k^2) to leave.]



 
 
=(G, =(, ), k, ℓ) be an instance of . 
Let v be a nice vertex and H_v be its haven. Then in any optimal solution opt() for , the total traveled length of all robots in  in H_v, as well as the total number of vertices of H_v visited by , is (k^4). 


 
    Assume, for contradiction, that the total length traveled of opt() inside H_v is at least c· k^4 + 2k + 1, where c is the constant in big-Oh notation of Lemma <ref>. Then by Lemma <ref>, we can turn opt() into a schedule S such that each robot moves exactly the same outside of H_v in both S and opt(), each robot passes an edge between H_v and the rest of the graph at most twice, and the total length traveled by all the robots inside H_v in S is at most c· k^4. But then the total length traveled in S is smaller than the total length traveled by opt(), which is a contradiction. 



 
 
=(G, =(, ), k, ℓ) be an instance of . 
Then in any optimal solution opt(), the total travelled length of any R ∈ that is at distance λ from a nice vertex is (λ· k + k^4).


 
    Assume for a contradiction that R ∈ starts at a vertex s_R∈ V(G) that is at distance λ from a nice vertex n_R, but the traveled length of R in opt() is at least 2λ· k +c_1· k^3 + c_2· k^4 +2k+1, where c_1 is the constant in the big-Oh notation from Lemma <ref> and c_2 is the constant in big-Oh notation from Lemma <ref>.

    We can now modify opt() by first moving R inside H_v, this can be done with total traveled length at most 2λ· k + c_1· k^3 by pushing all robots along a shortest s_R-n_R path to H_v using at most λ· k steps, reconfiguring inside of H_v using c_1· k^3 steps such that the robots that we pushed in H_v can leave back towards their starting positions using additional λ· k steps. Afterwards, we follow opt(), keeping R always in H_v and whenever a different robot interacts with H_v, we reconfigure it using Lemma <ref> to the position from which it needs to leave next. Let this schedule be S. Note that the total traveled length of S outside of H_v is at most 2λ· k + c_1· k^3 larger than the total traveled length of opt() outside of H_v and R stays in H_v after it entered it for the first time. By Lemma <ref>, we can adapt S to a schedule S' such that S' still does only at most 2λ· k + c_1· k^3 more steps outside of H_v than opt() does, but does at most 2k steps between H_v and G-H_v and at most c_2· k^4 steps inside of H_v, which contradicts the optimality.  



Before we are ready to prove the main theorem for this section, we first need the following lemma, which will allow us to restrict the movement of the free robots.

 

Let =(G, =(, ), k, ℓ) be an instance of .
For every R_i ∈ that is within distance λ_i from a nice vertex,
there is a set B(R_i, λ_i)  of vertices of cardinality k^(λ_i· k +k^4) such that, for any optimal solution opt(), there exists an optimal solution opt'() satisfying that, in opt'() R_i moves only on vertices in B(R_i, λ_i) and all the remaining robots move exactly the same in opt() and opt'().
 Moreover, B(R_i, λ_i) is computable in (|V(G)|+|E(G)|) time. 



First observe that if a vertex v has degree at least c_1· k^4+k+1, where c_1 is the constant from Lemma <ref>, then any connected subgraph H_v of G that consists of v and k^4+k+1  
many arbitrary neighbors of v is a haven. 
By Lemma <ref>, any optimal solution visits at most c_1· k^4+k vertices of H_v and hence also at most c_1· k^4+k neighbors of v. 
This is because every robot enters H_v at most once, and the total traveled length inside H_v is at most c_1· k^4. 
It follows that in any optimal schedule opt(), any free robot R_i that enters v does at most one step after entering v. 
Otherwise, we could get a shorter schedule by moving R_i, after entering v for the first time, directly to any neighbor of v in V(H_v) that is not visited by any robot. 
In addition, if opt() moves R_i outside H_v after visiting v, then we can modify the schedule opt() to obtain schedule opt'() in which R_i enters v and then moves to a neighbor w of v such that w∈ V(H_v) and w is not visited by any other robot in opt(). 
By Lemma <ref>, the total traveled length of any free robot R_i∈ is at most c_2(λ_i· k + k^4).
From the discussion above, to obtain B(R_i,λ_i), we only need to keep vertices that can be reached from the starting position s_i of R_i by a path P of length at most c_2(λ_i· k + k^4) such that only the penultimate vertex on P can have degree larger than c_1· k^4+k in G. 
Moreover, for every vertex that has degree larger than c_1· k^4+k, we only need to keep c_1· k^4+k arbitrary neighbors. 
It follows that we can obtain the set B(R_i, λ_i) by first a modified depth-bounded BFS from s_i, such that for any vertex v of degree at least c_1· k^4+k+1, we do not continue the BFS from this vertex. 
The depth of this BFS is bounded by  c_2(λ_i· k + k^4) and it is easy to see that the number of vertices marked by this BFS to be included in B(R_i, λ_i)  is at most (c_1· k^4+k+1)^1+ c_2(λ_i· k + k^4).
Afterwards, for every vertex in B(R_i, λ_i) with degree at least c_1· k^4+k+1, but with less than c_1· k^4+k+1 many neighbors in B(R_i, λ_i), we add arbitrary c_1· k^4+k+1 - |N_G(v)∩ B(R_i, λ_i)| many neighbors of v to B(R_i, λ_i). 
This concludes the construction of B(R_i, λ_i). 
It is easy to see that |B(R_i, λ_i)|≤ (c_1· k^4+k+1)^1+ c_2(λ_i· k + k^4)· (c_1· k^4+k+1) = k^(λ_i+k^4) and the lemma follows.



 

 Let =(G, =(,), k, ℓ) be an instance of . In -time, we can reduce  to p=g(k)-many instances (for some computable function g(k)) _1, …, _p such that there exists j ∈ [p] satisfying:  
 
     
  * If ={R_1} then _j=(G_j, _j=(_j, ∅), k_j, ℓ_j), where k_j ≤ k and ℓ_j ≤ℓ, is 
     a yes-instance of  if and only if  is a yes-instance.
    Moreover, in this case there is an optimal solution opt(_j) such that |opt(_j)| = _G_j(s_1, t_1)+(k^5), and for every robot R_i ∈_j ∖{R_1}, 
    the moves of R_i in opt(_j) are restricted to a vertex set of cardinality at most k^(k^4) that is computable in linear time. 
     
       
     
  * In polynomial time we can compute a schedule for _j with total traveled length at most ∑_R_i ∈_j(s_i, t_i) + (k^5), and given such a schedule for _j, in polynomial time we can compute a schedule for  of cost at most |opt()| + 
     (k^5).
    

Furthermore, every optimal schedule for  satisfies the property that every vertex in G is visited at most (k^5) many times in the schedule. 


    Let =(G, =(, ), k, ℓ) be an instance of , and let opt() denote an optimal schedule for . We give a nondeterministic reduction that produces a single instance _j=(G_j, R_j=(_j, ∅), k_j, ℓ_j), which can be made deterministic in -time.
    
    To construct _j, we will be making guesses about the initial and final segments of the robots' routes in opt(), which may lead to redefining the starting and final positions for some of them, with the purpose of getting them close to havens – as explained at the beginning of this section. The guessing is based on the types of the starting and final positions of the robots (see Lemma <ref>). We set ℓ_j=ℓ.

Case I.  If the starting or the final position of a robot is at distance at most 11k from a nice vertex, we do not change it. 

Case II.  If the starting or the final position of a robot is a type-(2) vertex on a path P that connects two nice vertices, then we look separately at all the robots that start on P and all the robots that end on P (guessing for each free robot whether it ends on P).
    Let us first consider the robots that start on P. 
    We make a guess, for each of these robots, about whether it ever leaves P, and if it does, from which endpoint of P it leaves for the first time. This splits the robots on P into three sets S_Left, S_Mid, S_Right. Observe that these three sets have to be “consecutive” on P (i.e., their robots respect the order of the sets), and we push the starting points of the robots in S_Left and in S_Right to distance at most k from the nice vertex they leave from for the first time. Similarly, we split the robots that end on P into the sets T_Left, T_Mid, T_Right. 
    We redefine the destinations of the robots in T_Left and T_Right to vertices at distance at most k from their respective nice vertices through which they enter P, and we compute the additional travel length incurred by moving them directly from these positions at distance at most k from  nice vertices to their destinations and subtract this number from ℓ_j.
    Recall that, according to our guess, S_Mid and T_Mid each contains precisely the robots that never leave P, and hence S_Mid=T_Mid.
              We show that for most of the robots in S_Mid, any optimal solution takes them directly from their starting positions to their destinations, except for those that start and end at distance at most k from the same nice vertex. 
    For those that do not start and end at distance at most k from the same nice vertex, 
    we compute the travel length incurred by taking them directly to their destinations, subtract it from ℓ_j, and delete these robots from .
    Finally, if S_Mid≠∅, then no robot can use P to move between its two endpoints. Moreover, if a robot is on P, then it does not need to go beyond the k-closest vertices on P to a nice vertex. Hence, if S_Mid≠∅, then we delete all the vertices on P that are at distance at least k+1 from a nice vertex.

Case III.  If the starting or the final position of a robot is a type-(3) vertex, which consists of a nice vertex n_R joined by a 2-path P to a vertex u in a connected subgraph C of size at most 8k, then we start by treating this situation the same as that of a type-(2) vertex, with the role of the second nice vertex replaced by u. 
    In particular, we guess the sets S_Left, S_Mid, S_Right, T_Left, T_Mid, T_Right,
         where S_Right (resp. T_Right) are the robots that start their routing by going from a vertex on P to u, or from u to a vertex on P. 
    We also change the starting and ending positions for the robots that are not in S_Mid to vertices that are at distance at most k from either n_R or u; we compute the routing that reflects this change, and subtract its travel length from ℓ_j.  
    
    If S_Mid≠∅, then the vertices on which the robots in S_Mid are positioned separate the robots that are in S_Right∪ T_Right plus the robots that start or end in C, from the rest of the graph. Note that at this point, there is no interaction between the robots in S_Right∪ T_Right∪ S_Mid and the other robots in . 
    Therefore, we can treat C and the part of P containing the robots in S_Right∪ T_Right∪ S_Mid as a separate instance, which has the same structure as that of a type-(4) vertex. We solve this instance optimally using Lemma <ref>, and keep on V(P) only the k-closest vertices to n_R. On the other hand, if S_Mid=∅ then some robots that start (resp. end) in S_Right (resp. T_Right) or in C might also visit n_R. 
    We show that, in the case of , 
    this happens only in a very restricted setting where the single robot in  starts or ends in C, which can be dealt with easily with the help of Lemma <ref>.
     On the other hand, if ||≥ 2, then this is no longer the case. We now further guess which of the robots that start (resp. end) in S_Right (resp. T_Right) or in C also visit n_R on the other end of P.  Using Proposition <ref>, we can show that we can always route these robots at the beginning (resp. at the end) to (resp. from) a position at distance at most k from n_R with overhead at most (k^3) over an optimal routing. Afterwards, we keep in G only the vertices on P at distance at most k from n_R, and remove the rest of V(C) ∪ V(P). 
    
    This concludes the reduction to obtain the instance _j from .

    Let us now prove Statement 1. 
    Observe that all the free robots can now be either at distance at most 11k from a nice vertex and we can use Lemma <ref> to compute the set B(R_i,11k)
    where they can move; or alternatively, they can be at distance at most k from a connected subgraph of size at most 8k associated with a type-(3) vertex and they will stay there, and hence, their movement in this case is restricted to 9k vertices.
    
    We now show how to compute a schedule for _j with total traveled length at most (s_1, t_1) + (k^5). To do so, we first move all the robots that are at distance at most 11k from a nice vertex v to a haven H_v of v. We then compute a shortest path P between s_1 and t_1. We note that P can only interact with a connected subgraph C of a type-(3) vertex at the beginning or at the end. In both cases, we can use  Lemma <ref> to compute an optimal routing of R_1 from C (resp. to) to the first (resp. from the last) haven P intersects.     
         Afterwards, all free robots on P are in havens. We let R_1 follow P. Whenever P interacts with a haven H that contains a free robot, we replace the subpath of P between the first interaction of R_1 with H and the last interaction of R_1 with H with a schedule computed by Lemma <ref> that reconfigures H taking R_1 between its two interaction positions. Each interaction with a haven increases the length of P by (k^3)  and there are at most k havens that contain a free robot. 
    Finally, we move the free robots at the end to their guessed destinations in _j.      We can show that this incurs a travel length of (k^5). 

    For Statement 2,  if ||=1 then Statement 2 follows from Statement 1. Otherwise, all starting positions and destinations are at distance at most 11k from nice vertices. Due to this, we can show that we can start by incurring an (k^2) travel length to route each robot to a nearest haven, and finish by incurring (k^4) travel length to route all the robots from havens at distance at most 11k from their destinations to their destinations. We can then route the robots one-by-one from a “starting” haven to a “destination” haven along a shortest path in the same manner we routed the robot R_1 in the case of . The routing of each robot incurs an overhead of (k^4) above its shortest path length, and hence the total overhead for routing all the robots between havens is (k^5) and Statement 2 follows.




Let =(G, =(, ), k, ℓ) be an instance of the problem, and let opt() denote an optimal schedule for . The reduction will produce a set of instances 
_1, …, _p, where p=g(k), such that one of the instances I_j, j ∈ [p], satisfies the statement of the theorem. For ease of presentation, we will present a nondeterministic reduction that produces a single instance _j=(G_j, R_j=(_j, ∅), k_j, ℓ_j), and the reduction can be made deterministic in -time to produce a set of [p] instance, one of them, _j, satisfies the statement of the theorem. We will assume that the reduction makes the right guesses; when we simulate the reduction deterministically, we will discard any enumeration resulting in inconsistent or incorrect guesses. To construct _j, we will be making guesses about the initial and final segments of the robots' routes in opt(), which may lead to redefining the starting and final positions for some of them. The guessing is based on the types of the starting and final positions of the robots (see Lemma <ref>). Set ℓ_j=ℓ.
 Let R be a robot located at a vertex v_R. If v_R is nice then we keep R at v_r. 

If v_R is a type-(1) vertex, then we do nothing.

If v_R is a type-(2) vertex, then v_R is on a 2-path P whose both endpoints are nice vertices, n_R and n'_R. (For visualization purposes, think about n'_R as being the “left” endpoint of P and n_R being its “right” endpoint.) Note that |P| > 6k (otherwise, R would be within distance 3k+1 from a nice vertex and v_R would be of type-(1)). Let S be the set of robots that occupy vertices on P. We guess a partition of S into three subsets S_Left, S_Mid, S_Right, where S_Left is the subset of robots such that the first nice vertex they visit is n'_R, S_Right is the subset of robots such that the first nice vertex they visit is n_R, and 
S_Mid is the set of robots that do not visit any nice vertex, and hence remain on P. Note that S_Left, S_Mid, S_Right may contain robots in . Observe that S_Left must be the |S_Left|-many closest robots in S to n'_R and S_Right must be the closest |S_Right|-many robots in S to n_R. We route the robots in S_Left and S_Right as follows. For each robot R' ∈ S_Left (resp. S_Right), move it towards n'_R (resp. n_R), pushing along robots on its way if needed, until the first time it reaches a vertex that is at distance at most k from n'_R (resp. n_R). 
Note that each robot in S_Left∪ S_Right is now within distance k from a nice vertex; let ℓ_1 be the total traveled length during this routing. We change the starting position of each robot in S_Left∪ S_Right in the instance  to its current position after the routing and subtract ℓ_1 from ℓ_j. 

If v_R is a type-(3) vertex, let C be the connected subgraph of size at most 8k that is connected by a 2-path P to a nice vertex n_R, and such that v_R ∈ V(C) ∪ V(P). If |P| ≤ 3k then we do nothing, as in this case v_R will be treated later as a type-(1) vertex. Let u_R be the vertex connecting P to C.

Suppose now that |P| > 3k, let S be the subset of robots occupying vertices in V(P) and let S_C be the set of robots occupying vertices in V(C). We treat this case similarly to how we treated type-(2) vertices with respect to n_R and u_R, and guess a partitioning of S into three subsets S_Left, S_Mid, S_Right, where S_Left is 
the subset of robots such that the first vertex with degree at least three in G they visit is n_R, S_Right is the subset of robots such that the first vertex with degree at least three in G they visit is u_R, and S_Mid is the subset of robots that do not visit any nice vertex nor visit u_R, and hence never leave P. We route the robots in S_Left and S_Right as follows. For each 
robot R' ∈ S_Left (resp. S_Right), move it towards n_R (resp. u_R), pushing along robots on its way if needed, until the first time it reaches a vertex that is at distance at most k from n_R (resp. u_R). 
  Let ℓ_2 be the total traveled length during this routing. We redefine the starting position of each robot in S_Left∪ S_Right in the instance _j to be its current position after the routing and subtract ℓ_2 from ℓ_j. 
Now if || = 1, then by Lemmas <ref> and <ref>, no free robot starts in P and either visits n_R and then comes back to C, or visits C and then visits n_R. We note that in the case that R_1 either starts or ends in C, it is possible that free robots in C cannot make way for R_1 to leave/enter C and need to leave through n_R. It is not difficult to see that in this case S_Right∪ S_Mid =∅. We can guess which robots in C need to enter n_R and use Lemma <ref> to compute a schedule with the minimum total traveled length that lets precisely these robots leave C toward n_R. Afterwards, we compute the routing of the guessed robots that takes them to vertices in B_Left and subtract the total traveled length of this routing from ℓ_j. We are done with this case for now. 
We note that, assuming that the guesses are correct, in all the above treatments, we maintain the equivalence between the two instances  and _j. The following treatment for the case where ||>1 may result in a non-equivalent instance as the treatment may result in an additive error of (k^4) steps. 

If || > 1, we guess which of the robots in S_Right∪ S_C visit n_R after visiting C and guess the order in which they leave C for the last time before they visit n_R for their first time. We know that the optimal solution does route these robots to leave towards n_R in this order, possibly with some additional robots entering C. Hence, it must be possible to reorder these robots as in their guessed order. Note that during this reordering, the remaining robots in S_C∪ S_Right might need to move to some positions in C or on the closest k vertices to C. We guess the exact positions where they end after this reordering, and let these guessed positions be their new starting positions. By   Proposition <ref>, in (k^3) steps, we can reconfigure the robots that leave through n_R in the correct order on P and the remaining robots in S_C∪ S_Right to their new starting positions. 
Afterwards, we can move these robots to S_Left and shift their starting positions to be at distance at most k from n_R as we did above for the robots that started in S_Left. Let ℓ_3 be the total traveled length during this rerouting. We subtract ℓ_3 from ℓ_j.

For a robot R ∈, let t_R be its destination. 

If t_R is within distance 11k from a nice vertex (which includes t_R being a type-(1) vertex), then we distinguish three cases depending on whether the current starting position s'_R of R is also at distance at most 11k from a nice vertex, or s'_R is of type-(2), or s'_R is of type-(3). If s'_R is at distance at most 11k from a nice vertex, we do nothing. If s'_R is of type-(2), since it is not close to a nice vertex, then our guess for R was that it would never leave the path P associated with this type-(2) vertex.  We treat this case as we do below as if t_R were a type-(2) vertex. 
If s'_R is of type-(3), since it is not close to a nice vertex, then our guess for R was that it would never leave P∪ C, where P and C, respectively, are the 2-path and the connected subgraph associated with this type-(3) vertex. We treat this case as we do below as if t_R were a type-(3) vertex.



 

  
If t_R is a type-(2) vertex, which is on a 2-path P whose endpoints n_R and n'_R are nice, then for each R' ∈, guess whether it ends on P and guess its relative position on P with respect to all the robots in  that end on P. Note that such a robot R' either visits a nice vertex in opt(), in which case its starting position is at distance at most 11k from a nice vertex, in which case we can assume that it ends on a vertex in B(R',11k) (see Lemma <ref>) and only allow the guess that R' ends on P if P intersects B(R',11k). 
Alternatively, if R' starts on P and never leaves it,  it will be either later removed from _j, or restricted to k vertices on P that are closest to either n'_R or n_R. In either case, we can restrict the moves of R' to a set B(R') of vertices satisfying |B(R')|= k^(k^4).

Now let T be the set of robots that end on vertices on P. We guess a partitioning of T into three subsets T_Left, T_Mid, T_Right, where T_Left is the subset of robots such that the last nice vertex they visit is n'_R, T_Right is the subset of robots such that the last nice vertex they visit is n_R, and T_Mid is the subset of robots that do not visit any nice vertex, and hence never leave P. Note that T_Mid has to be equal to the set S_Mid that was guessed above while considering the types of the starting positions of the robots w.r.t. P. 
   
Let B_Left and B_Right be the sequences of the k closest vertices on P_R to n'_R and to n_R, respectively. For each robot R_i ∈ T_Left,  
let x_i be the number of robots in T_Left∪ T_Mid whose relative position on P is farther from n'_R than that of R_i. 
If R_i has a destination t_i, we define a new destination t'_i for R_i to be the vertex on P whose distance from n'_R is equal to min{_G(n'_R, t_i), k-x_i}. On the other hand, if R_i ∈, then we guess t'_i to be any position at distance at most k-x_i from n'_R that conforms to the guessed relative position of R_i with respect to the other robots on P.
We do the same for the robots in T_Right. 

For robots in T_Left, we now compute the routing that takes each robot R_i from t'_i to t_i directly, if needed pushing along the (free) robots (note that this might include free robots in T_Mid) on its way. We let ℓ_3 be the total traveled length during this computed routing and we subtract ℓ_3 from ℓ_j.


If T_Mid≠∅, let R_i∈ T_Mid∩ be a robot with starting position s_i and destination t_i. If 
{s_i,t_i}⊆ B_Left, then we do nothing with R_i. Notice that all robots in S_Left must have their starting positions closer to n'_R than s_i and all robots in T_Left must have their destinations closer to n'_R than t_i; therefore, none of the changes that we did to the starting positions and the destinations of robots in S_Left∪ T_Left affects R_i. We do the same if {s_i,t_i}⊆ B_Right. 
For the remaining robots in T_Mid∩, we compute the routing that takes them directly from their starting positions to their destinations, possibly pushing along free robots in T_Mid. We let the total distance traveled by all these robots in T_Mid during this routing be ℓ_4, we subtract ℓ_4 from ℓ_j, and 
we then remove these robots, as well as all the robots they pushed, from the instance. It is not difficult to see that in opt() the travel length incurred by these robots is precisely ℓ_4. This is because the robots in T_Mid have to be in a sense ordered on P. 
In addition, if a robot R' uses P only to avoid other robots passing through a nice vertex n'_R (resp. n_R), after R' enters P from n'_R (resp. n_R), if R leaves P through the same nice vertex n'_R (resp. n_R), then R' will remain in B_Left (resp. B_Right). Therefore, we can start by moving any of these robots in T_Mid that start away from B_Left and B_Right towards their destinations, possibly pushing some robots just outside of these buffers closer to their destinations. Then we can follow an optimal solution to move the robots in T_Left and T_Right to their destinations in _j when all the robots on P are in the correct final relative order, and lastly just navigate each robot directly to its destination.

Observe now that what we are left to deal with are the robots in ∩ T_Mid, which appear either as the first or last sequence of robots in T_Mid w.r.t. P. 
Note that, if there is such a robot R_i whose s_i is not in 
 B_Left∪ B_Right, then we do not need to do anything since any traveled length incurred by R_i has already been accounted for in the previous cases, and we can remove R_i from the instance. Suppose now that s_i is in one of the two buffers, say B_Left. If there is a robot in T_Left that pushes R_i outside of B_Left, then when we computed its final routing contribution to ℓ_3, the travel length incurred by R_i has been already accounted for. So now we can assume that the final position of R_i is in B_Left. We guess the final position of t_i of R_i in B_Left. Note that the robots that we kept in _j have their starting positions and their destinations in B_Left∪ B_Right. If T_Mid was non-empty at the beginning, this means that P cannot be used by any robots to go between n'_R and n_R, and in this case we remove V(P)∖(B_Left∪ B_Right) from the graph.
 
If t_R is a type-(3) vertex, let C be the connected subgraph of size at most 8k that is connected by a 2-path P to a nice vertex n_R, and such that v_R ∈ V(C) ∪ V(P). If |P| ≤ 3k then we do nothing, as in this case t_R will be treated later as a type-(1) vertex. Let u_R be the vertex connecting P to C.

Similarly to how we treated the type-(2) vertices above, for each R' ∈, we guess whether it ends on P and guess its relative position on P with respect to all the robots in  that end on P. If a robot in  does not end on P, we guess whether it ends in C, and in which case we also guess the exact vertex in C on which the robot ends. 
Again, as in the above treatment of type-(2) vertices, R' either visits a nice vertex in opt(), in which case its starting position is at distance at most 11k from a nice vertex in _j, and in this case we can assume that it ends on a vertex in B(R',11k) (see Lemma <ref>), and only allow the guess that R' ends on C∪ P if V(P∪ C) intersects B(R',11k). Alternatively, if R' starts on P∪ C and never leaves it, in which case it will be either later removed from _j, restricted to k vertices on P that are closest to n_R, or restricted to C and the k vertices on P closest to u_R. In either case, we can restrict the moves of R' in an optimal solution to a set B(R') of vertices, where |B(R')|= k^(k^4).


Now let T be the set of robots that end on P and T_C be the set of robots that end in C. We guess a partitioning of T into three subsets T_Left, T_Mid, T_Right, where T_Left is the subset of robots such that the last degree three vertex they visit is n_R, T_Right is the subset of robots such that the last degree three vertex they visit is u_R, and T_Mid is the subset of robots that do not visit any nice vertex, and hence never leave P. Note that T_Mid has to be the same as the set S_Mid that was guessed above while considering the types of the starting positions of the robots w.r.t. P. 


Let B_Left be the sequence of the k closest vertices on P to n_R. For each robot R_i ∈ T_Left,  
let x_i be the sum of the number of robots in T_C and the number of robots in T whose relative destination on P is farther from n_R than that of R_i. 
If R_i has destination t_i, we define a new destination t'_i for R_i to be the vertex in B_Left whose distance from n_R is equal to min{_G(n'_R, t_i), k-x_i}. On the other hand, if R_i is in , then we guess a destination t'_i for R_i from among the positions at distance at most k-x_i from n_R conforming to the guessed relative destinations with respect to the other robots on P.

For the robots in T_Left, we now compute the routing that takes each robot R_i from t'_i to t_i directly, if needed pushing along the (free) robots (note that this might include free robots in T_Mid) on its way. We let ℓ_5 be the total traveled length during this computed routing and we subtract ℓ_5 from ℓ_j.


If T_Mid≠∅, then we observe that T_Mid separates the robots in T_Mid∪ T_Right∪ T_C from the rest of the instance. This means that the remaining robots cannot use C to change their order on P, and since their destinations are either in V(G)∖(V(P)∪ V(C)) or in B_Left, they never need to enter vertices of V(P)∖ B_Left. (Note that in the modified instance, the destinations of the robots in T_Left have been changed to vertices in B_Left.) If a robot in T_Mid starts and ends in B_Left, it still might need to be pushed around by other robots in the solution; let T'_Mid be the set of robots in T_Mid∪ T_Right∪ T_C except those in T_Mid that start and end in B_Left. We now use Lemma <ref> to compute an optimal routing for T'_Mid in G[V(P)∪ V(C)]. Note that since P has length at least 3k, there is an optimal solution that starts by moving the robots that start in B_Left outside of B_Left, routes the robots so that the robots whose destinations in C are on their correct destinations, and such that the robots with destinations on P are positioned on vertices in V(P)∖ B_Left in the correct relative position without any robot ever entering B_Left and finishes by routing the robots on P directly to their destinations. Let ℓ_6 be the total traveled length during this optimal routing. We subtract ℓ_6 from ℓ_j, remove the robots in T'_Mid from the instance and the vertices in V(C)∪ (V(P)∖ B_Left) from the graph. 


Now, if T_Mid=∅, we treat T_Right similarly to T_Left. That is, we define B_Right to be the sequence of the k closest vertices on P to u_R. For a robot R_i ∈ T_Right, we let x_i be the sum of the number of robots in T_C and the number of robots in T whose relative destinations on P are farther from n_R than that of R_i (i.e., closer to u_R). 

If R_i has destination t_i, we define a new destination t'_i for R_i to be the vertex in B_Right whose distance from u_R is equal to min{_G(u_R, t_i), x_i+1}. On the other hand, if R_i is in , then we guess a destination t'_i for R_i from among the positions at distance at most x_i+1 from u_R conforming to the guessed relative destination of R_i with respect to the other robots on P. We now compute the routing that takes each robot R_i∈ T_Right from t'_i to t_i directly, if needed pushing along the (free) robots (note that this might include free robots in T_Mid) on its way. We let ℓ_7 be the total traveled length during this computed routing and we subtract ℓ_7 from ℓ_j.

Now if || = 1,
then by Lemmas <ref> and <ref>, no robot starts in P ∪ C and either visits n_R and then comes back to C, or visits C and then visits n_R, and we are done with this case. We recall that, assuming that the guesses are correct, in all the above treatments for the destination vertices, we maintain the equivalence between the two instances  and _j. The following treatment for the case where ||>1 may result in non-equivalent instance, as the treatment may result in an additive error of (k^4) steps.

If || > 1, we guess which of the robots in T_Right∪ T_C visit n_R before visiting C and guess the order in which they leave n_R for the last time before they visit C; denote the set of these robots by T_n_R^C. For every such robot R_i, we now define a new destination t”_i in B_Left in the same manner as we did for the robots in T_Left and move R_i to T_Left (and remove it from T_Right∪ T_C). 
We know that the optimal solution does route each robot R_i from t”_i to t'_i. To upper bound the contribution of such reconfiguration to the total traveled length, we observe that after all of these robots are at their positions t”_i and only the remaining robots in T_Right∪ T_C are in V(C)∪ (V(P)∖ B_Left), then the robot (T_Right∪ T_C)∖ T_n_R^C are in V(C)∪ B_Right (they will not need to move since we moved them when considering the starting positions in V(C)∪ V(P)), and we can route the robots in T_n_R^C first to the buffer B_Right by going directly there, maybe pushing some of the robots in B_Right closer to u_R. Afterwards, we use Proposition <ref> to move the robots in the correct order in B_Right in (k^3) steps. 
 Let ℓ_8 be the total traveled length during this reconfiguration. 
 We subtract ℓ_8 from ℓ_j and remove the robots left in T_C∪ T_Right from the instance and the vertices in V(C)∪ (V(P)∖ B_Left) from the graph.
 
Now, we know that the optimal solution does route these robots to leave towards C in this order possibly even interacting with some robots that started in C, but do not end there.  Moreover, we can use the algorithm of Lemma <ref> to reconfigure these robots in the correct order on P. Afterwards, we can move these robots to S_Right and shift their starting positions to B_Right in the same manner as we did above for the robots that started in S_Right. Let ℓ_9 be the total traveled length during this reconfiguration. 
 We subtract ℓ_9 from ℓ_j.


Observe that some of the free robots still do not have destinations, but may have remained in the instance. According to our guesses, each such robot R is either within a distance at most 11k from some nice vertex, or starts in a type-(3) vertex such that the 2-path P associated with that type-(3) vertex has length at least 3k, and never leaves C∪ B_Right, where C is the connected subgraph of size at most 8k associated with that type-(3) vertex and B_Right is the buffer of k vertices on P that are closest to C. By Lemma <ref>, we can assume that in opt() the moves of every free robot R that is at distance at most 11k from a nice vertex are restricted to B(R,11k). 
Moreover, B(R,11k) has cardinality k^O(k^4) and is computable in (|V(G)| + |E(G)|) time. We can guess the vertex in B(R,11k) that R ends up on in opt() and assign it as its final destination in _j. Define B(R) = B(R,11k) in this case.
Now for each free robot R that is in V(C) ∪ B_Right and never leaves it, we guess which vertex, out of the at most 9k vertices in V(C) ∪ B_Right it ends up on in the optimal solution guessed above, and assign it as its final destination in _j. Define B(R) = V(C) ∪ B_Right in this case. 


Let _j=(G_j, _j=(_j, ∅), k_j, ℓ_j) be the resulting instance from the above. It is clear that k_j ≤ k since we never added any robots to the instance. Moreover, in the case where ||=1, assuming the guesses are correct, the equivalence between the two instances  and _j follows (as argued above). Now to show in this case that for any optimal solution opt(_j) of _j, we have |opt(_j)|=_G_j(s_1, t_1) + (k^5), where R_1 is the only robot in , let P_1 be a shortest path in G_j between s_1 and t_1, and note that |P_1|=_G_j(s_1, t_1). Observe that every robot is now positioned at distance at most 11k from a nice vertex in G_j, or it is at a distance at most k from some connected subgraph C of a type-(3) vertex and will never visit the nice vertex associated with that type-(3) vertex. For every nice vertex w, let H_w be the haven associated with w as in Definition <ref>.
First, we move all the robots within distance 11k from w into H_w.  

Observe that P_1 can only interact with the connected subgraph C of a type-(3) vertex either at the beginning of P_1 before visiting any havens, or at the end when it will no longer visit a haven afterwards. This is true since P_1 is a (simple) shortest path and each such connected subgraph C is separated by a nice vertex from the rest of the graph. Suppose s_1 is at distance at most k from such a connected subgraph C separated by a nice vertex n_R; the argument is similar in the case where t_1 is at  distance at most k from C. Note that all the robots that are at a distance at most k from C are the robots that visit C before visiting n_R. Moreover, in an optimal solution, no such robot (other than R_1) visits n_R, as stipulated by the guess and Lemma <ref>. Hence, the optimal solution does reconfigure these robots in such a way that R_1 is the closest robot to n_R among all of them, or reconfigure R_1 to its destination in C. In either of these cases, by Proposition <ref>,  we can perform this reconfiguration using at most O(k^3) steps. After this reconfiguration (and similar one at the end of the routing), all the robots on P_1 are in havens. 

Let us now iteratively modify P_1 to a final routing of R_1 in which R_1 enters and leaves each haven at most once. Note that there are at most k havens that contain at least one robot and we repeat the following process at most k times each increasing the length of the routing by at most (k^3). Let H_w be the first haven in which R_1 collides with a robot on P_1. Let v_first be the first vertex in H_w that R_1 visits on P_1 and let v_last be the last vertex in H_w it visits on P_1. We first reconfigure the robots on H_w such that v_first is empty. This can be done using at most k-1 steps (at most k-1 robots each doing one step). Now we follow P_1 until it enters v_first. Afterwards, we use Lemma <ref> to reconfigure the set of all robots that are currently in H_w to obtain a resulting configuration in which R_1 is at v_last. The cost of this reconfiguration is (k^3), and since this process is repeated at most k times, the overall additional cost incurred is (k^4). 

Note that technically in _j, _j can contain other robots that R_1 and all these robots have destinations. However, all the robots that we did not navigate to the correct destinations are at the moment in havens, so the additional loss to the optimal solution that we did not account for to navigate R_1 from its destination in _j (which is close to the haven) to its destination in  cannot be more than (k^3), as it interacts in this case with at most one haven. Hence, we can assume that each of these robots is at distance at most (k^3) from its destination, and we can iteratively navigate them to their destinations (which are close to havens), each incurring at most (k^4) reconfiguration steps. 

It follows that there is a schedule for R_1 of cost _G_j(s_1, t_1) + (k^5), and the first part of Statement 1 of the theorem holds. Moreover, every robot in _j other than R_1 has been assigned a final destination and its movement has been restricted to a set of vertices B(R) of cardinality at most k^(k^4), and the second part of Statement 1 of the theorem holds as well.
 
Let us now prove Statement 2 of the theorem, which states that in polynomial time we can compute a schedule for _j with total traveled length at most f(k)+∑_R_i ∈_j(s_i, t_i), and given such a schedule for I_j, in polynomial time we can compute a schedule for  of cost at most |opt()| + 
     δ(k), for some computable function δ.

First notice that all the modifications to the instance, except for those performed in the treatment of type-(3) vertices, preserve the optimality of the solution. In addition, in the treatment of type-(3) vertices, the additional possible cost over that of the optimal solution is (k^4) to let all the robots first leave the connected subgraphs associated with type-(3) vertices and only after all the robots that wish to leave have left, the robots that need to enter can enter. This means that whenever we have a schedule for _j of cost opt(_j) + x, for some x∈ℕ, we can get a solution for  of cost  opt(_j) + x+(k^4). This establishes the second part of Statement 2 of the theorem. Also observe that opt(_j)≥∑_R_i ∈_j(s_i, t_i). 
Note that thanks to this treatment of type-(3) vertices,  all the starting positions and the destinations of the robots are at distance at most 11k from  nice vertices. We start by pushing all the robots to the closest haven to their starting position. This takes at most (k^2) many steps. We temporarily choose for each robot R_i an arbitrary destination t'_i in the haven that is closest to its final destination t_i. 
Note that this increases the distance of each robot to its destination by (k) many steps. Now for each robot R_i, we compute a shortest path P_i from its current position in a haven to t'_i. We navigate each robot R_i along P_i to t'_i, treating the collisions in havens in exactly the same manner as we did for robot R_1 when proving  Statement 1 of the theorem. This incurs a total cost of ∑_R_i ∈_j(s_i, t_i)+ O(k^5). For each haven H_w, compute a BFS tree rooted at w that spans the haven and the destinations of the robots that are in it. If two subtrees corresponding to havens H_u and H_w overlap, then we route all robots in H_u to H_w (note that the largest distance between two havens in a connected cluster is at most 22k^2). This incurs a cost of (k^3) steps overall. 
Afterwards, compute once again for the haven H_w a BFS tree rooted at w spanning each haven and the destinations of the robots in it. Now we can reconfigure the robots so that they are on the path w to their destinations in the BFS tree and the robots on the same leaf-to-root path are in the same relative order as their destinations. This reconfiguration incurs a cost of (k^4). Afterwards, each robot is at distance (k^2) from its destination and we can send the robots directly to their destinations along the leaf-to-root path in the BFS tree. This incurs an additional (k^3) many steps. Hence, the total traveled length by all robots is is ∑_R_i ∈_j(s_i, t_i)+ O(k^5).

Finally, all the modifications performed while reducing  to _j, except for those (k^4) steps needed in the treatment of type-(3) vertices, can be characterized as direct moves to each robot R_i (without going back-and-forth) between two vertices that R_i must visit in this order in opt(). Therefore, the optimal solution on which the guess for _j is based, does take R_i from its starting position in  to its starting position in _j, then to its terminal position in _j and finally from its terminal position in . If we just sum up these distances, and using the fact that optimal length for I_j is at most ∑_R_i ∈_j(s_i, t_i)+ O(k^5), we can conclude that opt() can do only at most (k^5) steps that are not moving R_i closer to either its start in _j, its destination in _j or its destination in , and hence any vertex cannot be visited by a robot more than (k^5) times.
 
 


The approximation algorithm claimed in the introduction (restated below) follows directly from Statement 2 of Theorem <ref>.

*




§ AN  ALGORITHM FOR  PARAMETERIZED BY K


The aim of this section is to establish Theorem <ref> by using Theorem <ref>. 

*


Let =(G, =(,), k, ℓ) be an instance of . By Statement 1 of Theorem <ref>, in -time we can compute an equivalent instance _j=(G_j, _j=(_j, ∅), k_j, ℓ_j) to  satisfying that k_j ≤ k and |opt(_j)| = _G_j(s_1, t_1)+(k^5), where ={R_1}. Moreover, the moves of every robot R_i ∈_j ∖{R_1} in opt(_j) are restricted to a vertex-set B(R_i) of cardinality at most k^(k^4) that is computable in linear time.

We define a state graph Q whose vertices are k_j-tuples with coordinates representing the positions of the robots. The first coordinate corresponds to R_1 and ranges over V(G_j); for 2 ≤ i ≤ k_j, the i-th coordinate encodes
the possible location of R_i and ranges over B(R_i). We purge any tuple in which a vertex in V(G_j) appears in more than one coordinate of the tuple. Since |B(R_i)| =k^(k^4), for i ∈{2, …, k_j}, it follows that the number of vertices in Q is at most n · k^(k^5). Two vertices/states S and S' in Q are adjacent if there is a valid (i.e., causing no collision) single (parallel) move for the robots from their locations in S to their locations in S'; the weight of an edge (S, S') in Q is the number of robots in S that have moved (i.e., their positions have changed). 

We now compute a shortest path (using Dijkstra's algorithm) between the  starting configuration S_start in Q, which is the k_j-tuple whose coordinates correspond to the starting positions of the robots in _j, and the configuration S_final corresponding to the destinations of the robots in _j.   We accept the instance  if and only if the weight of the computed shortest path is at most ℓ_j. The running time of the algorithm is n^2 · k^(k^5).    





Let =(G, =(,), k, ℓ) be an instance of . By Statement 1 of Theorem <ref>, in -time we can compute an equivalent instance _j=(G_j, _j=(_j, ∅), k_j, ℓ_j) to  satisfying that k_j ≤ k and |opt(_j)| = _G_j(s_1, t_1)+(k^5), where ={R_1}. Moreover, for every robot R_i ∈_j ∖{R_1}, 
    the moves of R_i in opt(_j) are restricted to the vertices of a vertex-set B(R_i) of cardinality at most k^(k^4) that is computable in linear time.

    
 
Define a state graph Q whose vertices are k-tuples with coordinates defined as follows. The first coordinate of a k_j-tuple corresponds to R_1 and can be any of the at most n vertices in V(G_j); the i-th coordinate of a tuple, where i ∈{2, …, k_j}, encodes the possible location of R_i and is confined to the vertices in B(R_i). We purge any tuple in which a vertex in V(G_j) appears in more than one coordinate of the tuple (i.e., is occupied by more than one robot in the same time step). Since |B(R_i)| =k^(k^4), for i ∈{2, …, k_j}, it follows that the number of vertices in Q is at most (n · k^(k^5)). Two vertices/states S and S' in Q are adjacent if there is a valid (i.e., causing no collision) single (parallel) move for the robots from their locations in S to their locations in S'; the weight of an edge (S, S') in Q is the number of robots in S that have moved (i.e., their positions have changed). 

Define the starting configuration S_start in Q to be the k_j-tuple whose coordinates correspond to the starting positions of the robots in _j. Define S_final to be the k_j-tuple whose coordinates correspond to the destinations of the robots in _j. Now compute a shortest (weighted) path from S_start to S_final in Q (e.g., using Dijkstra's algorithm) and accept the instance  if and only if the weight of the computed shortest path is at most ℓ_j. The running time of the algorithm is (|V( Q)|^2)=(n^2 · k^(k^5)), and it is clear that the above algorithm decides the instance correctly. It follows that  is  parameterized by k.
 

 

§ AN  ALGORITHM PARAMETERIZED BY TREEWIDTH AND K






In this section, we present an  algorithm for  parameterized by the number of robots and the treewidth of the input graph combined. 
This result implies that the problem is  on certain graph classes such as graphs of bounded outerplanarity, which include subgrids of bounded height. In this sense, the result can be seen as complementary to the recently established -hardness of the problem on bounded-height subgrids <cit.>.



 §.§ Terminology and Observations


 We begin by setting up the required terminology and proving some observations used for our algorithm.
[Semi-routes]
	A semi-route for R_i is a tuple W_i=(u^i_0, …, u^i_t) such that each u^i_j is either a vertex of G or the symbol , and such that (i) u^i_0=s_i and moreover, if R_i ∈, then u^i_t=t_i, and (ii) ∀ j ∈ [t], either u^i_j-1 =u^i_j or u^i_j-1u^i_j∈ E(G) or one out of u^i_j-1 and u^i_j is the symbol . 
 The notion of two conflicting semi-routes is identical to that for routes, except that we only consider time steps where neither semi-routes has . 
Formally, two semi-routes W_i=(u^i_0, …, u^i_t) and W_j=(u^j_0, …, u^j_t), where i ≠ j ∈ [k], are non-conflicting if (i) ∀ r ∈{0, …, t}, either u^i_r= or u^j_r= or
 u^i_r ≠ u^j_r, and (ii) ∄ r ∈{0, …, t-1} such that u^j_r+1 =u^i_r and u^i_r+1 =u^j_r and ∉{u^i_r,u^i_r+1,u^j_r, u^j_r+1}. Otherwise, we say that W_i and W_j conflict.



Intuitively, the above definition gives us a notion of partial routes, where the robots can be thought of as having become “invisible” (but still potentially in motion) for some time steps during a route (assume only a small part of the graph is visible to us). These time steps where a robot disappears from view are represented by the symbol . Note that a robot can “reappear” at a different vertex than the one it “disappeared” at. A semi-schedule for  is a set of semi-routes during a time interval [0, t] that are pairwise non-conflicting.  The  length of a semi-route and a semi-schedule is naturally defined as the number of time steps in which the robot moves from one vertex to a different vertex, and the total traveled length of a semi-schedule is the sum of the lengths of its semi-routes.
A boundaried graph <cit.> is a graph G with a set X⊆ V(G) of distinguished vertices called boundary vertices; the set X is called the boundary of G. A boundaried graph (G,X)  is called  a p-boundaried graph if |X|≤ p. A p-boundaried subgraph of  a graph G is a p-boundaried graph (H,Z) such that (i) H is a vertex-induced subgraph of G and (ii) Z separates V(H)∖ Z from V(G)∖ V(H).  



In what follows, let =(G, =(, ), k, ℓ) be an instance of . Let (H,Z) be a p-boundaried subgraph of G with  boundary Z containing all the terminals. Let S be a schedule for this instance with routes W_i, i∈ [k].  





[Signatures of Schedules]
Call the tuples in the set (Z∪{↑,↓})^k, configuration tuples for (H,Z).
We define the signature of the schedule S with respect to (H,Z) as a sequence of tuples τ_0,…, τ_t, where each τ_i is a configuration tuple defined as follows: the j^th coordinate of τ_i signifies whether at the end of time step i 
  * R_j is on a vertex v∈ Z, in which case this value is v; or 
  * whether it is inside H but not on the boundary, in which case this value is ↓; or 
  * whether it is disjoint from H, in which case this value is  ↑. 
 	
 
The tuple τ_i is called the signature of the schedule S with respect to (H,Z) at time step i. The tuple τ_0 and τ_t are called starting and ending configuration tuples. 






[Checkpoints of Schedules]
We say that the schedule S:

  * externally affects (H,Z) at time steps i and i+1 if some robot moves from a vertex outside H to a vertex in Z during time step i+1, or if some robot moves from some vertex of Z to a vertex outside H during time step i+1. That is, for some robot R_j, we either have that  u^j_i∉ V(H) and u^j_i+1∈ Z, or we have u^j_i∈ Z and u^j_i+1∉ V(H). 

  * internally affects (H,Z) at time steps i and i+1 if some robot moves from a vertex of H to a vertex of Z during time step i+1, or if some robot moves from some vertex of Z to a vertex in H during  time step i+1. 
That is, for some robot R_j, we have u^j_i≠ u^j_i+1 and moreover, we either have that u^j_i∈ V(H) and u^j_i+1∈ Z or we have u^j_i∈ Z and u^j_i+1∈ V(H).

  * affects (H,Z) at time steps i and i+1 if it internally or externally affects (H,Z) at time steps i and i+1. 

The pairs of consecutive time steps at which the schedule affects (H,Z) are called checkpoints of the schedule with respect to (H,Z). 
We drop the explicit reference to (H,Z) whenever it is clear from the context. 
Two checkpoints (x,x+1) and (y,y+1) are said to be consecutive if x<y and there is no checkpoint (z,z+1) such that x<z<y. 
 

Roughly speaking, the checkpoints are the time steps at which the schedule interacts in some way with the separator Z. The interaction involves a robot either moving to or from a vertex of Z. As a result, the notion of checkpoints enables one to “decompose” a solution along the vertices of Z between consecutive checkpoints. We will argue that whenever Z is sufficiently small, the number of possible checkpoints will also be small.
 

[v-Rigid Pairs]
	Let v∈ Z. A pair of configuration tuples (τ_1,τ_2) is a v-rigid pair if there is a unique coordinate j in which these tuples differ, exactly one out of τ_1[j],τ_2[j] is equal to v and exactly one out of τ_1[j],τ_2[j] is equal to ↓. 
	
	
	The above definition is useful when considering checkpoints where the schedule internally affects (H,Z) with the restriction that exactly one robot moves into Z from V(H)∖ Z or from Z into V(H)∖ Z.  

[Semi-schedules]
A semi-schedule with respect to (H,Z) is a semi-schedule where every vertex on every semi-route is contained in V(H) and for every subtuple (u,,…, ,v) in a semi-route, where u,v∈ V(H), it must be the case that u,v∈ Z. 
 		

The intuition here is that whenever the robot “vanishes” or “reappears”, it happens at the boundary Z. This allows us to analyze how a schedule interacts with the subgraph H since every movement between H and the rest of G must happen through the boundary Z.


	[Signatures of Semi-schedules]
	The signature τ_0,…, τ_t of a semi-schedule with respect to (H,Z) is defined similarly to that of a schedule after making the assumption that  denotes a vertex outside H, that is,  we have the symbol ↑ in the j^th coordinate of tuple τ_i if and only if the robot R_j has u^j_i=. 
	A semi-schedule externally affects (H,Z) at time steps i and i+1 if some robot “moves”  from  to Z during time step i+1 or it “moves” from Z to  during time step i+1. That is, for some robot R_j, we have u^j_i= and u^j_i+1∈ Z or we have u^j_i∈ Z and u^j_i+1=. 
 	 The notions of internally affecting (H,Z), affecting (H,Z), checkpoints with respect to (H,Z) are defined exactly as for schedules. 



[Checkpoint Tuples]
Checkpoint tuples of a schedule or semi-schedule S with respect to (H,Z) are defined as those configuration tuples for (H,Z) that appear in the signature of S at the time steps participating in checkpoints of S with respect to (H,Z). The checkpoint tuple sequence of S with respect to (H,Z) is the set of checkpoint tuples ordered according to their respective time steps.



Our dynamic programming algorithm will make use of the following observation about signatures of schedules and semi-schedules to narrow down the search space. 


Let τ_0,…, τ_t be the signature of a schedule or semi-schedule with respect to (H,Z). Then, the following properties hold:


  * τ_0=(s_1,…,s_k). Moreover, the coordinates of τ_t that correspond to the robots in  are fixed, that is, τ_t=(t_1,…,t_||,v_1,…,v_k-||) for some vertices v_1,…, v_k-|| distinct from {t_1,…,t_||}.
 
  * The first two and last two tuples in the signature are at checkpoints. That is, (0,1) and (t-1,t) are checkpoints.
	
  * Let (x,x+1),(y,y+1) be consecutive checkpoints such that x+1<y. Then, the tuples τ_x+2,…, τ_y-1 are identical. 
	
  * Let (x,x+1) be a checkpoint. There is a coordinate j such that  τ_x[j]≠τ_x+1[j] and at least one of τ_x[j] or  τ_x+1[j] is a vertex of Z.
	
  * Let (x,x+1) be a checkpoint. There is no coordinate j such that  τ_x[j] = ↑ and τ_x+1[j]= ↓ or τ_x[j]= ↓ and τ_x+1[j]= ↑.	
	
  * For every time step x, τ_x contains at most one occurrence of any vertex of Z.
	
  * Let (x,x+1) be a checkpoint and suppose that τ_x[j]≠ v∈ Z and τ_x+1[j]=v. 
	Then, either there is no j' such that τ_x[j']=v or it must be the case that τ_x+1[j']≠ v. 
	 	
  * Parallel movements between vertices of the boundary Z in a single time step must happen along edges that exist and moreover, no edge can be used by two robots. 
	



	
	
	
	 
		The first two statements follow from the fact that the terminals are contained in Z. The third, fourth and fifth statements follow from the definition of checkpoints and the fact that the boundary is a separator between V(H)∖ Z and V(G)∖ V(H). The sixth and seventh statements are due to the fact that no vertex can be occupied by two robots at the same time. The eighth statement is due to the fact that a schedule or semi-schedule must be comprised of pairwise non-conflicting routes or semi-routes. 
	 










 §.§ Using Bounded Checkpoints to Solve the Problem on Bounded Treewidth Graphs




Let =(G, =(, ), k, ℓ) be an instance of . Let (H,Z) be a p-boundaried subgraph of G with  boundary Z containing all the terminals. 
	 If there is a schedule S for  in which each vertex is entered by any robot
    at most ν(k) times, then the following hold.
 
  * The number of checkpoints of S with respect to (H,Z) is bounded by (pk·ν(k)). 
  * The number of possible checkpoint tuple sequences of  S with respect to (H,Z) is bounded by g(k,p)=p^(pk·ν(k)). 
 

  
From Definition <ref>, we have that the number of checkpoints of S with respect to (H,Z) is bounded by (pk·ν(k)). This is because each of the p vertices in Z can be visited at most ν(k) times by any of the k robots. Moreover, the number of possible choices for a specific checkpoint tuple is bounded by (p+2)^k. This is simply because these are configuration tuples. This gives us the stated bound on the number of possible checkpoint tuple sequences of S with respect to (H,Z).  
 


We now proceed by defining the partial solutions which play a central role in our algorithm. 






[Partial Solutions]
Let =(G, =(, ), k, ℓ) be an instance of . Let (H,Z) be a p-boundaried subgraph of G with  boundary Z containing all the terminals. 
Given an ordered set of configuration tuples γ_1,…, γ_q for (H,Z) where q is even, γ_1 is a starting configuration tuple and γ_q is an ending configuration tuple, a partial solution corresponding to the sequence (γ_1,γ_2),…, (γ_q-1,γ_q) is a semi-schedule S with respect to (H,Z) such that the checkpoint tuple sequence of S with respect to (H,Z) is exactly these tuples in this order. That is, the checkpoints of S with respect to (H,Z) are (x_1,x_2),…,(x_q-1,x_q) and τ_x_i=γ_i for each i∈ [q]. 








  §.§.§ Dynamic Programming over Tree Decompositions



*


Let =(G, =(, ), k, ℓ) be the given instance of . 
   We start with a tree decomposition (T,β) of G of optimal width and add the terminals to every bag. Call the resulting tree decomposition (T,β') and let its width be w.  By invoking Theorem <ref> and setting ν(k)=(k^5) in Observation <ref>, we infer that the length of the checkpoint tuple sequence of S with respect to each boundaried graph (G_x,T^↓,β'(x)) where x∈ V(T), is at most twice the number of checkpoints in this sequence. Hence, the length of this checkpoint tuple sequence is bounded by λ(k,w)=(wk^6). Here, G_x,T^↓ denotes the graph induced by the vertices that lie either in the bag β'(x) or below it.
Moreover, by the same observation, the number of possible checkpoint tuple sequences of S with respect to each boundaried graph (G_x,T^↓,β'(x)) is at most g(k,w+1)=w^(wk^6).

Based on this fact, our goal is to use dynamic programming to compute, for every x∈ V(T) and boundaried graph (G_x,T^↓,β'(x)), and for every possible checkpoint tuple sequence of length at most λ(k,w) with respect to this boundaried graph, the length of the best partial solution corresponding to this checkpoint tuple sequence within the boundaried graph. 
 When x is the root node,  G_x,T^↓ is exactly the input graph G. Hence, the solution is given by the minimum entry in the table computed at the root node. Note that we only describe an algorithm to compute the length of an optimal solution. However, it is straightforward to see that an optimal schedule can also be produced in the same running time. 







Let =(G, =(, ), k, ℓ) be the given instance of . 
We assume that a schedule exists. This can be checked in polynomial time <cit.>. Let ρ denote the upper bound on the size of an optimal schedule given by our additive approximation. If ℓ≥ρ, then we are done. So assume this is not the case.

We start with a nice tree decomposition (T,β) of G of optimal width. This can be computed using Proposition <ref>. Now, add the terminals to every bag. Call the resulting tree decomposition (T,β') and let its width be w.  Note that although we have added the terminals to all the bags, the tree T has remained the same. Hence, we just have a slightly modified version of  nice tree decompositions, where  the root bag and every leaf bag is exactly the set of terminals. However, the remaining nodes (introduce, forget, join) are as described in Definition <ref>. 
Moreover, we have the mapping γ':V(T)→ 2^V(G) defined as γ'(t)=⋃_u≼ tβ'(u). 


By invoking Theorem <ref> and setting ν(k)=(k^5) in Observation <ref>, we infer that the length of the checkpoint tuple sequence of S with respect to each boundaried graph (G_x,T^↓,β'(x)) where x∈ V(T) is at most twice the number of checkpoints in this sequence and so, is bounded by λ(k,w)=(wk^6). Moreover, by the same observation, the number of possible checkpoint tuple sequences of S with respect to each boundaried graph (G_x,T^↓,β'(x)) where x∈ V(T), is at most g(k,w+1)=w^(wk^6).

Based on this fact, 
our goal is to compute, for every x∈ V(T) and boundaried graph (G_x,T^↓,β'(x)), and for every possible checkpoint tuple sequence of length at most λ(k,w) with respect to this boundaried graph, the length of the best partial solution corresponding to this checkpoint tuple sequence within the boundaried graph. For “infeasible” checkpoint tuple sequences, we assign them a length of  ρ+1 to indicate infeasibility. When x is the root node,  G_x,T^↓ is exactly the input graph G. Hence, the solution is given by the minimum entry in the table computed at the root node. Note that we only describe an algorithm to compute the length of an optimal solution. However, it will be straightforward to see that an optimal schedule can also be produced in the same running time. 



Consider a node x∈ V(T) and let C_x denote the set of possible configuration tuples over β'(x). That is, C_x=(β'(x)∪{↑,↓})^k. For every sequence σ=((τ_1,τ_2),…,(τ_s,τ_s+1)) where each τ_i∈ C_x, we say that σ is a sequence at x. Moreover,  σ is called good if Properties 1-2 and Properties 4-8 listed in Observation <ref> hold. Any other sequence at x is bad. The length of the sequence σ described above is s+1. 

For every good sequence σ at x of length at most λ(k,w), we define h^x_σ to be the value of the best partial solution corresponding to σ in the boundaried graph (G_x,T^↓,β'(x)). For every bad sequence σ at x of length at most λ(k,w), h^x_σ is defined as ρ+1. This is just to indicate that we do not look for partial solutions corresponding to these sequences as satisfying the properties in Observation <ref> is a necessary condition for a sequence to correspond to checkpoint tuples. Note that for a given sequence σ of length at most λ(k,w), it is straightforward to check the relevant properties from Observation <ref> and thus determine whether it is good or bad in time λ(k,w)n^(1). 

We next proceed to the description of the computation of our dynamic programming table.  Every bad sequence σ of length at most λ(k,w) is identified at every bag and h_σ is set to ρ+1. As standard, we next proceed bottom up, starting from the leaf nodes. 






    Leaf node.
 At each leaf node x, and every good sequence σ at x of length at most  λ(k,w) ,  h^x_σ is computed by brute force since the graphs have at most w+1 vertices. 


 



    Forget node.

Let x be a forget node with child node y. Let v be the unique vertex in β'(y)∖β'(x).
Let σ be a good sequence of length at most λ(k,w) at the node x. We compute h^x_σ as follows.



  * Let Σ_v denote the set of all sequences obtained from σ by going over all possible ways of substituting some occurrences of ↓ in σ with v. 

Since there are at most (w+1)·λ(k,w) occurrences of ↓ in σ, the size of the set Σ_v is bounded by λ'(k,w)=2^(w+1)·λ(k,w). 
 
The idea behind this step is to “guess”, in the partial solution corresponding to σ, all instances where a movement is made from a vertex in β'(x) to the forgotten vertex v or from v to a vertex in β'(x).  
Once this is done, we would still need to “guess” all instances where a movement is made from v to a vertex not in β'(x) or vice-versa. Since x is a forget node, all such movements from v must go “below” to the vertices in γ'(y)∖β'(y) and vice-versa. This guess is done next. 


  * Let Σ'_v denote the set of all sequences obtained by going over every sequence σ' in Σ_v and inserting at most λ(k,w) v-rigid pairs of tuples belonging to C_y (see Definition <ref>) between the elements of σ' in all possible ways. 

 For each sequence σ' in Σ_v, the number of resulting sequences is at most (k· (w+2)^k)^λ(k,w). This is because there are 2k· (w+2)^k possible v-rigid pairs (fix the coordinate of v and allow all possible entries in the remaining coordinates) and at most λ(k,w) possible positions. Hence, the set Σ'_v has size at most λ”(k,w)=λ'(k,w)· (k· (w+2)^k)^λ(k,w). 





As discussed in the last step, the goal of this step is to guess all steps where a movement is made from v to a vertex not in β'(x) or in the other direction, in which case the robot must move to or from γ'(y)∖β'(y). This is why we have the requirement of replacing v with ↓ or vice-versa in consecutive tuples, motivating Definition <ref>. Moreover, we only need to guess pairs of tuples where only the coordinate that has v is changed, because all other pairs would already be in the sequence σ and all occurrences of v in these pairs guessed correctly in the previous step. 


  * Inductively, for every good sequence σ' in Σ'_v of length at most λ(k,w), we would have computed h^y_σ' at the node y. 

Hence, h^x_σ is defined to be the mimimum h^y_σ' where σ' ranges over all good sequences of length at most λ(k,w) in the set Σ'_v. 

The correctness is a consequence of the fact that our guesses in the first two steps exhaustively explore, for a partial solution S corresponding to σ, all possible checkpoint tuples of S with respect to (G_y,T^↓,β'(y)).
 







    Introduce node.

Let x be an introduce node with child node y. Let v be the unique vertex in β'(x)∖β'(y). Let σ be a good sequence of length at most λ(k,w) at the node x. We compute h^x_σ as follows.



  * Let μ denote the total number of moves made in σ from v to vertices of β'(y) or vice-versa. That is, μ denotes the number of pairs (τ_i,τ_i+1) in σ such that for some j, either τ_i[j]=v and τ_i+1[j]=v' for some v'∈β'(y) or τ_i[j]=v' and τ_i+1[j]=v for some v'∈β'(y). 

The idea behind this step is to separate the required partial solution corresponding to σ into two parts – one part for all the moves between v and β'(y) and the second part will then be a semi-schedule that is a partial solution corresponding to an appropriate sequence at the child node y. Notice that there cannot be a move made directly from v to vertices of γ'(y)∖β'(y) because x is an introduce node and so, v is separated from γ'(y)∖β'(y) by β'(y).

	
  * Let σ' denote the sequence obtained from σ  by replacing every occurrence of v with ↑ and remove all pairs of tuples that are identical.
The idea in this step is to focus on the part of the partial solution corresponding to σ (call it S) that lies in the boundaried graph (G_y,T^↓,β'(y)), which is a semi-schedule (call it S') with respect to (G_y,T^↓,β'(y)). Since v is a vertex outside (G_y,T^↓), all occurrences of v must be treated as an “external” vertex and so, we replace these occurrences with ↑. If this results in a pair (τ_i,τ_i+1) where the tuples are identical, then this pair cannot be a pair of checkpoint tuples of S' with respect to (G_y,T^↓,β'(y)) and so, we remove these.

	
  * Finally, h^x_σ is defined to be μ plus the value of h^y_σ' at the node y.
	 
	




    Join node.

Let x be a join node with children nodes y_1 and y_2.
Let σ be a good sequence of length at most λ(k,w) at the node x. 
Let μ denote the total number of moves made in σ between vertices of β'(y).
That is, μ denotes the number of tuples (u,v,τ_i,τ_i+1,j) where u,v∈β'(y), 
(τ_i,τ_i+1) is a pair in σ, τ_i[j]=u and τ_i+1[j]=v. 



We now compute h^x_σ as follows. 


  * Let Σ' denote the set of all sequences obtained from σ by going over every occurrence of ↓ in σ, and replacing it with one out of  or . 

The set Σ' has size at most λ'(k,w) by the same reasoning as that used in the first step of processing forget nodes.

 
 The idea in this step is to “guess”, for every occurrence of a vertex of γ'(x)∖β'(x) in σ (which is indicated by ↓), whether this vertex is in γ'(y_1)∖β'(y_1) (denoted by ) or in γ'(y_2)∖β'(y_2) (denoted by ) in some partial solution S corresponding to σ. 
 

  * Let Σ” denote pairs  (σ_1,σ_2) of sequences obtained as follows.
For every σ'∈Σ' do:

  * In σ', replace all occurrences of  with ↓ and replace all occurrences of  with ↑. Call the result σ_1.  
  * In σ', replace all occurrences of  with ↑ and replace all occurrences of  with ↓. Call the result σ_2. 

  * Add the pair (σ_1,σ_2) to Σ”. 

	



The idea in this step is to generate, for every guess made in the first step, two sequences σ_1 and σ_2, expressing the checkpoint tuple sequences of S with respect to the boundaried graphs (G_y_1,T^↓,β'(y_1)) and (G_y_2,T^↓,β'(y_2)), respectively.    Hence, to obtain σ_1, the vertices “guessed” to be below β'(y_2) are denoted by ↑ 
and the vertices “guessed” to be below β'(y_1) are denoted by ↓. Similarly, to obtain σ_2, the vertices “guessed” to be below β'(y_1) are denoted by ↑ 
and the vertices “guessed” to be below β'(y_2) are denoted by ↓.

We next use the fact that the length of S can be expressed as the sum of the lengths of partial solutions S_1 and S_2 corresponding to σ_1 and σ_2 minus the number of movements made between vertices of β'(x) to avoid double counting these moves.  


  * Hence, h^x_σ is defined to be the minimum over all h^y_1_σ_1+h^y_2_σ_2-μ where we range over all pairs  (σ_1,σ_2)∈Σ” where both σ_1 and σ_2 are good sequences. If such σ_1 and σ_2 do not exist, then h^x_σ is set to ρ+1 to indicate infeasibility.  







 

The number of entries at each bag of the tree decomposition as well as the time required to compute the table at each bag is clearly FPT in k and w. This completes the proof of Theorem <ref>. 
 





    
    
                   
      
 
     
 
            
    
  
   
                               
 
       




        



§ USING THE TOTAL ENERGY AS THE PARAMETER

In the final part of our paper, we consider the complexity of  in settings where we are dealing with many robots but the energy budget ℓ is small. While intuitively this may seem like an “easier” case due to the fact that ℓ immediately bounds the number of robots that will end up moving in a hypothetical schedule, we show that the problem (and even its restriction to the often-studied case where all robots have destinations) is unlikely to be fixed-parameter tractable when parameterized by ℓ. 
 

 *


We provide a parameterized reduction from the well-known [1]-complete Multicolored Clique problem <cit.>: decide whether a given κ-partite graph (V_1,…,V_κ,E) contains a clique of size κ. To avoid any confusion, we explicitly remark that in this proof we use κ to denote the parameter of the initial instance of Multicolored Clique and not the number of robots in the resulting instance of .

Our reduction takes an instance (V_1,…,V_κ,E) of Multicolored Clique and constructs an instance (G,=(,),κ',ℓ) of  as follows. To obtain G, we: 


  * subdivide each edge e∈ E κ^3 many times; 

  * attach a single new pendant vertex v' to each vertex v∈ V_1∪…∪ V_κ in the original graph; and

  * for each pair of integers i,j such that 1≤ i< j≤κ, construct a new vertex s_i,j and make it adjacent to every vertex in V_i, and construct a new vertex t_i,j and make it adjacent to every vertex in V_j.

For =(, ), we set =∅ and add two sets of robots into . First, for each vertex v in V_1∪…∪ V_κ, we construct a blocking robot r^v and set v as its starting point as well as its destination.
Second, for each of the newly constructed s_i,j∈ V(G), we construct a clique robot r^i,j, set s_i,j as its starting point and t_i,j as its destination. Finally, we set ℓ:=2κ+κ 2· (κ^3+3) and κ':=||. This completes the description of our reduction.

Towards proving correctness, we first observe that a hypothetical schedule for (G,,κ',ℓ) can never use less than ℓ:=2κ+κ 2· (κ^3+3) travel length. Indeed, there are κ 2 many clique robots, and the shortest path between their starting and destination points has length κ^3+3. Moreover, every schedule must route each clique robot r^i,j through at least one vertex in V_i and at least one vertex in V_j, and hence a hypothetical solution must spend a length of at least 2 to move at least one of the blocking robots in each V_p, p∈ [κ], out of the way and then back to its initial position (which is also its destination).

Now, assume that (G,,κ',ℓ) is a yes-instance. By the argument above, this implies that there is a schedule which moves precisely one of the blocking robots in each V_p, p∈ [κ]; let us denote by w_p the starting vertex of the unique blocking robot which is moved from V_p. Since (G,,κ',ℓ) is a yes-instance, E must contain an edge between each w_i and w_j, 1≤ i<j≤κ; in particular, these vertices induce a clique in (V_1,…,V_κ,E).

For the converse, assume that (V_1,…,V_κ,E) contains a κ-clique w_1,…,w_κ. We construct a solution for (G,,κ',ℓ) as follows. First, for each robot starting at w_i, i∈ [κ], we spend a length of 1 to move it to the pendant vertex w_i'. Next, we route each robot r^i,j from s_i,j to w_i, through the (κ^3+1)-length path to w_j (whereas the existence of this path is guaranteed by the existence of the edge w_iw_j∈ E), and then to its destination t_i,j. Finally, we route each blocking robot which originally started at w_i back to w_i from w'_i. The travelled length of this schedule is precisely 2κ+κ 2· (κ^3+3), as desired.
 


As mentioned in the introduction, we complement Theorem <ref> with a fixed-parameter algorithm on graph classes of bounded local treewidth.

Before proceeding to the proof, we recall the syntax of Monadic Second Order Logic (MSO) of graphs. It contains the logical connectives ∨, , , 
⇔, ⇒, variables for vertices, edges, sets of vertices and sets of edges, and the quantifiers ∀ and ∃, which can be applied to these variables. It also contains the following binary relations: (i) u∈ U, where u is a vertex variable and U is a vertex set variable; (ii) d ∈ D, where d is an edge variable and D is an edge set variable;
(iii) 𝐢𝐧𝐜(d,u), where d is an edge variable, u is a vertex variable, with the interpretation  that the edge d is incident to u; 
(iv)  equality of variables representing vertices, edges, vertex sets and edge sets. 
 
 The well-known Courcelle's theorem <cit.> states that checking whether a given graph G models a given MSO formula ϕ can be done in  time parameterized by the treewidth of G and the size of ϕ. Morover, this result holds even if some vertices of G are given labels or colors (i.e., we allow a fixed number of additional unary relations over V(G)). This is because one can produce an equivalent graph G' such that G has bounded treewidth if and only if G' does, plus an alternate MSO formula ϕ' such that G models ϕ if and only if G' models ϕ'. 
 

*







	Let =(G, =(, ), k, ℓ) be the given instance of  where G belongs to a graph class that is closed under taking subgraphs and in which the treewidth of a graph of diameter d is bounded by f(d) for some function f. Let ' denote the set of those robots in  whose final position is distinct from the starting position. Since each of the robots in ' must move at least one step, it follows that if |'|>ℓ, then the instance is a no-instance. So, assume that |'|≤ℓ. Let U denote the set of starting points of the robots in '. 

 Consider an optimal schedule S. We say that an edge e appears in a route W=(u_0, …, u_t) in S if the endpoints of e are the vertices u_j-1 and u_j for some j∈ [t]. We say that e appears in S if it appears in some route in S. Let E_S denote the set of edges of G that appear in S. We observe that every connected component of the subgraph of G induced by E_S (call it G_S) contains a vertex of U. If this were not the case and there is a connected component of G_S disjoint from U, then we can delete all the routes whose edges appear in this connected component and still have a feasible schedule for the given instance, contradicting the optimality of S.  Moreover, since S has total energy at most ℓ, it follows that at most ℓ edges can appear in S. Hence, it follows that S is contained in the subgraph H defined as the union of the subgraphs induced by the ℓ-balls centered at the starting positions of the robots in '. 
    
   
 
Notice that since H is obtained by taking the union of at most ℓ graphs, each of diameter at most 2ℓ, it follows that H has diameter at most 2ℓ^2 and so, the treewidth of H is upper bounded by f(2ℓ^2). It remains to argue that  is FPT parameterized by the energy and treewidth of the input graph. We do this by making some guesses, obtaining a bounded number of MSO formulas such that input is a yes-instance if and only if at least one of these formulas is true on the graph H with a label function (with constant number of labels) and then invoking Courcelle's theorem <cit.>. Let ” denote the subset of ∖' contained in H and let '=∩ V(H).







	
	Suppose that α≤ℓ robots move in S and let the routes in S be {W_i=(v^i_1,…,v^i_d_i)| i∈ [α]}. Assume that the first |'| routes, W_1,…,W_|'|, correspond to the robots in '.   We guess α and d_1,…, d_α as these are all at most ℓ. Moreover, we guess, for  every pair of vertices v^i_j and v^p_q whether they are equal. Let this be expressed by a function μ(v^i_j,v^p_q) that evaluates to 1 if and only if these vertices are guessed to be equal. 
	Thus, even though we do not know the actual vertices in the solution (except for the starting and endpoint positions of the robots in '), this guess gives us the “structure” of the entire solution. Notice that the number of guesses is bounded by a function of ℓ.
		Now, we consider the labeled graph H where the starting points of all robots in '∖” are labeled red and the starting points of the robots in ” are labeled blue. Fix a guess of α, the numbers d_1,…,d_α and a guess of the function μ and express the following as an MSO formula.  

There are ordered vertex sets {W_i=(v^i_1,…,v^i_d_i)| i∈ [α]} such that the following hold:
 
  * Each W_i is a walk in H.

  * For every i,j,p,q, v^i_j and v^p_q are equal if and only if μ(v^i_j,v^p_q) is 1.

  * The walks W_i are pairwise non-conflicting routes.
 
  * For each of the first |'| walks W_1,…,W_|'|, the initial and final vertices are precisely the starting and ending points, respectively, of some robot in '.

  * For each labeled vertex appearing on any walk W_i, this vertex must be the first vertex of some walk W_i.

  * For each walk W_i starting at a blue vertex, it must terminate at the same blue vertex. 
 	


Expressing the above in MSO is straightforward to do, so we do not go in to lower level details of the MSO formula.

We next argue that the input is a yes-instance if and only if there is a guess of α,  the numbers d_1,…,d_α and a guess of the function μ such that the resulting MSO formula is true on H. Consider the forward direction. An optimal schedule S with routes W_1,…,W_α naturally gives us a “correct” guess of α,  d_1,…,d_α and the function μ. Moreover notice that Properties 1-4 are clearly satisfied. For Property 5, notice that only the starting points of robots that never move can be disjoint from the set of initial vertices of the routes {W_i| i∈ [α]} in the optimal schedule S. Since these robots do not move, they also cannot appear on any route W_i or they would obstruct a robot that moves. Finally, Property 6 is satisfied since every robot in ” that moves also ends up returning to its starting point. The converse is trivial.
   


 
 
 

§ CONCLUSION

 
 In this paper, we presented parameterized algorithms for fundamental coordinated motion planning problems on graphs. In particular, we proved that is fixed-parameter tractable parameterized by the number of robots, and that is fixed-parameter tractable parameterized by the number k of robots and the treewidth of the input graph combined. This latter result implies that  is fixed-parameter tractable in several graph classes which may be of interest w.r.t. application domains, including graphs of bounded outerplanarity. 

 We conclude by highlighting three directions that may be pursued in future works:
  
 

  * Is   parameterized by k (alone) on planar graphs, or even on general graphs? 

  

  * What is the complexity of  on trees? While  is known to be in  on trees, the complexity of the general problem on trees remains unresolved.


  * The focus of this paper was on minimizing the travel length/energy, which is one of the most-studied optimization objectives. Nevertheless, there are other important objectives, most notably that of minimizing the makespan. It seems that at least in the settings considered here, optimizing the makespan may be a computationally more challenging problem.
 In particular, the question of whether  Coordinated Motion Planning on trees is  parameterized by k remains open.

   

   




