Parameterized Complexity of Efficient Sortation
Robert Ganian Hung P. Hoang Simon Wietheger


Bayesian Nonparametric Inference in McKean-Vlasov models
    Richard Nickl  [Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, email: nickl@maths.cam.ac.uk]    Grigorios A. Pavliotis [Department of Mathematics, Imperial College London, email: g.pavliotis@imperial.ac.uk, kolyan.ray@imperial.ac.uk]    Kolyan Ray ^† 
    
=====================================================================================================================================================================================================================================================================================================



 
A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing.
We study this problem under the recent graph-theoretic formalization of Van Dyk, Klause, Koenemann and Megow (IPCO 2024). The problem asks  —given an input digraph D (the fulfillment network) together with a set of commodities represented as source-sink tuples—for a minimum-outdegree subgraph H of the transitive closure of D that contains a source-sink route for each of the commodities. Given the underlying motivation, we study two variants of the problem which differ in whether the routes for the commodities are assumed to be given, or can be chosen arbitrarily.
Statements where proofs or more details are provided in the appendix are marked with . A full version of the manuscript will be made available on arXiv.



We perform a thorough parameterized analysis of the complexity of both problems. Our results concentrate on three fundamental parameterizations of the problem: 


  * When attempting to parameterize by the target outdegree of H, we show that the problems are para-hard even in highly restricted cases;

  * When parameterizing by the number of commodities, we utilize Ramsey-type arguments, kernelization and treewidth reduction techniques to obtain parameterized algorithms for both problems;

  * When parameterizing by the structure of D, we establish fixed-parameter tractability for both problems w.r.t. treewidth, maximum degree and the maximum routing length. We combine this with lower bounds which  show that omitting any of the three parameters results in para-hardness.

  



                              


§ INTRODUCTION


The task of finding optimal solutions to logistical challenges has motivated the study of a wide range of computational graph problems including, e.g., the classical Vertex and Edge Disjoint Paths <cit.> problems and Coordinated Motion Planning (also known as Multiagent Pathfinding) <cit.>. And yet, when dealing with logistical challenges at a higher scale, collision avoidance (which is the main goal in the aforementioned two problems) is no longer relevant and one needs to consider different factors when optimizing or designing a logistical network. In this paper, we focus on parcel sortation, a central aspect of contemporary large-scale logistical networks which has not yet been thoroughly investigated from an algorithmic and complexity-theoretic perspective.

In the considered setting, we are given an underlying fulfillment network and a set of commodities each represented as a source and destination node. The nodes in the fulfillment network typically represent facilities at various locations, and each commodity needs to be routed from its current facility s_i (e.g., a large warehouse) to a facility t_i in the vicinity of the end customer. However, when routing parceled commodities in the network, each parcel that travels from s_i to t_i via some internal node u must be sorted at u for its subsequent downstream node. Hence, if multiple commodities arrive at u and each need to be routed to a different facility downstream, it is necessary to apply sortation at u to subdivide the stream of incoming parcels between the next stops; in large-scale operations u would typically be equipped with a designated sort point for each downstream node, and the number of sort points that a node can feasibly have is typically limited. On the other hand, if all the commodities arriving at u were to then be routed to the same downstream node, one can avoid the costly sortation step at u (via applying containerization at a previous facility and using a process called cross-docking at u). We refer readers interested in a more detailed description of these processes to recent works on the topic <cit.>. 
  
In their recent work, Van Dyk, Klause, Koenemann and Megow <cit.> have shown that the task of optimizing parcel sortation in a logistical network can be modeled as a surprisingly “clean” digraph problem. 
Indeed, if one models the network as a digraph D and each commodity as (s_i, t_i, P_i) where P_i is an s_i-t_i-path in D, the aim is to find a sorting network—a subgraph of the transitive closure of D—with minimum outdegree. 
The sorting network captures the information of sort points at each node: which downstream nodes that the node has a sort point for.
As we want to control the number of sort points at each node, this translates to the objective of minimizing the outdegree. 
While Van Dyk, Klause, Koenemann and Megow <cit.> primarily focused their work on the lower-level optimization task of computing the sorting plans when the physical routes of the commodities are fixed, in this work we additionally consider the higher-level optimization task where we can determine the routes as well as sort points. 
This gives rise to the following two problem formulations[For purely complexity-theoretic reasons, here we consider the decision variants; all algorithmic results obtained in this article are constructive and can also solve the corresponding optimization tasks.]: 
 


	Min-Degree Sort Point Problem ()
	A digraph D=(V,E), a target T∈ and a set K of routed commodities each of which is a tuple of the form (s,t,P) where s, t ∈ V and P is an s-t-path in D.	
 	Is there a subgraph H of the transitive closure (D) of D such that the maximum outdegree of H is at most T, and for every commodity (s,t,P) ∈ K, there exists a directed s-t-path in H ∩(P)?

  


	Min-Degree Routing and Sort Point Problem ()
	A digraph D=(V,E), a target T∈ and a set K⊆ V× V of commodities.
	Is there a subgraph H of (D) such that the maximum outdegree of H is at most T and for every commodity (s,t) ∈ K, there exists a directed s-t-path in H?


An example illustrating these problems is provided in Figure <ref>.
Note that for  the paths of commodities are not fixed and hence commodities are defined as 2-tuples.
 

While both  and  could be rather easily shown to be -complete on general graphs, Van Dyk, Klause, Koenemann and Megow showed that the former problem remains -complete even when restricted to orientations of stars <cit.>. In the rest of their article, they then focused on obtaining approximation as well as exact algorithms for  on special classes of oriented trees. Apart from these individual results, the computational complexity of  and remains entirely unexplored.

Contributions.  The central mission of this article is to provide a (near-)comprehensive parameterized analysis of the complexity of  and , with the aim of identifying precise conditions under which the problems become tractable. Our analysis will, in fact, reveal that the complexity-theoretic behavior of these problems is surprising and sometimes very different from the complexity of classical routing problems such as Vertex Disjoint Paths.
 Towards achieving our goal, we consider three natural types of parameterizations for the considered problems: parameterizing by the target solution quality (i.e., T), by the number of commodities, or by the structural properties of the input graph. The article is accordingly split into three parts, one for each of these perspectives.
 
In the first part of our article—Section <ref>—we establish that  remains -hard already when T=2. Turning to , we show that here -hardness holds already for the case of T=1. While the proofs of these results are non-trivial and work even on highly restricted inputs, this section is the least technically challenging of the three.

In Section <ref>, we turn towards an analysis of the considered problems when parameterized by the number of commodities. 
For both problems, we begin by establishing fixed-parameter tractability for the case of T=1 via a direct and stand-alone algorithm, as our more involved arguments for the general cases do not seemlessly transfer to this simpler setting. For , we then obtain a fixed-parameter algorithm for the general case by a kernelization argument that combines two main ingredients: a non-trivial data reduction rule that allows us to reduce the size of each “well-behaved” intersection of paths, and a Ramsey-type argument which guarantees that—after some simple preprocessing—every sufficiently large instance will contain some “well-behaved” intersection of paths.
  We note that the proof of this result is already more challenging than those required in Section <ref>, and the situation becomes even more difficult when we turn to . 
 
In order to solve  when T≥ 2, we first develop a preprocessing procedure which reduces the input into an equivalent one such that the length of every directed path is upper-bounded by a function of the parameter. This result can, on its own, already serve as the main ingredient of an  algorithm for  on general graphs. It is perhaps worth noting that—in spite of some superficial similarity between the problems—the -tractability of  contrasts the known para-hardness of Vertex Disjoint Paths (parameterized by the number of paths) on directed graphs <cit.>.
  
While it remains open whether the aforementioned -tractability can be improved to a fixed-parameter algorithm for on general graphs w.r.t. the number of commodities,
 we conclude the section by showing that the problem is fixed-parameter tractable when the input digraph is planar.  The proof of this result employs a further preprocessing procedure which does not result in a problem kernel, but instead obtains a graph of bounded radius. Even though bounded-radius planar graphs are known to have bounded treewidth <cit.>, we still cannot use this to solve the problem directly by, e.g., applying Courcelle's Theorem <cit.> since the transitive closure need not have bounded treewidth. 
We complete the proof by branching to determine a bounded-size “template” which characterizes the structure of the sought-after solution, and then using Courcelle's Theorem to check whether this template can be realized in the instance.
 

In Section <ref>, we target graph-structural parameterizations which would allow us to solve  and  for arbitrary choices of T and arbitrarily many commodities. Given the previously established -hardness of on orientations of stars—and the fact that the same reduction also works for —one could ask whether parameterizing by treewidth plus the maximum vertex degree (of the underlying undirected graph) suffices; after all, this combined parameterization has already been successfully employed to achieve fixed-parameter algorithms for a number of other challenging problems, including, e.g., Edge Disjoint Paths <cit.>. Unfortunately, our reductions in Section <ref> already establish the -hardness of both problems of interest even on bounded-degree trees.

As our final contribution, we show that the intractability of both problems can be overcome if one takes the maximum length of any admissible route as a third parameter. In particular, we devise a fixed-parameter algorithm that relies on dynamic programming to solve both  and  when parameterized by the treewidth and maximum degree of the input graph (or, more precisely, its underlying undirected graph) plus the maximum length of a route in a solution. We complement this result with lower bounds which prove that all three of these parameters are necessary: dropping any of the three results in -hardness for both problems. 

A summary of our complexity results for the two problems is provided in <Ref>.



  

§ PRELIMINARIES

For k ∈, we denote by [k] the set 1, …, k. 
We employ standard graph-theoretic terminology <cit.>.
For a directed graph D = (V,E), let Δ_D^+(v) and Δ_D^-(v) be the sets of out-neighbors and in-neighbors of v, respectively, for all v∈ V.
Let δ_D^+(v) = |Δ_D^+(v)|, δ_D^-(v) = |Δ_D^-(v)|, δ^+(D) = max_v∈ Vδ_D^+(v), and δ^-(D) = max_v∈ Vδ_D^-(v). 
We may omit the subscript where D is clear from context. 
We use D[X] to denote the sub(di)graph of D induced on the vertex set X. The transitive closure of D, denoted by (D), is the directed graph on the vertex set V(D), whereas an edge (i,j) exists in (D) if and only if there is a directed path from i to j in D.
The underlying undirected graph of a directed graph D, denoted by D, is the undirected simple graph obtained from D by replacing each directed edge with an undirected one.

We assume familiarity with basic terminology in the area of parameterized complexity, including fixed-parameter tractability, kernelization, -tractability and para-hardness <cit.>. A reduction rule is safe if it transforms the input instance ℐ into an instance ℐ' such that ℐ is a YES-instance if and only if so is ℐ'. ()


Graph Terminology.
We employ standard graph-theoretic terminology <cit.>.
For a directed graph D = (V,E), let Δ_D^+(v) and Δ_D^-(v) be the sets of out-neighbors and in-neighbors of v, respectively, for all v∈ V.
Let δ_D^+(v) = |Δ_D^+(v)|, δ_D^-(v) = |Δ_D^-(v)|, δ^+(D) = max_v∈ Vδ_D^+(v), and δ^-(D) = max_v∈ Vδ_D^-(v). 
We may omit the subscript where D is clear from context.  
 For u,v ∈ V, a path in D from u to v is called a u-v-path.
For two graphs D, D', we say that D' is a subgraph of D and write D'⊆ D if V(D')⊆ V(D') and E(D') ⊆ E(D).
The induced subgraph D[X] of a vertex set X⊆ V(D) is defined by V(D[X]) = X and E(D[X]) = (X× X) ∩ E(D).
 The transitive closure of D, denoted by (D), is the directed graph on the vertex set V(D), whereas an edge (i,j) exists in (D) if and only if there is a directed path from i to j in D.


Let G be a connected undirected graph.
For two vertices of v and v', denote by (v,v') the length of a shortest path from v to v' in G.
The eccentricity of a vertex v in G is defined as max_v' ∈ V(G)(v,v'), and the radius of G is the minimum eccentricity over all vertices of G.
The underlying undirected graph of a directed graph D, denoted by D, is the undirected simple graph obtained from D by replacing each directed edge with an undirected one.

Parameterized Complexity.
In parameterized complexity <cit.>, the complexity of a problem is studied not only with respect to the input size, but also with respect to some problem parameter(s). 
The core idea behind parameterized complexity is that the combinatorial explosion resulting from the -hardness of a problem can sometimes be confined to certain structural parameters that are small in practical settings. 
Formal definitions are provided below.

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 () if there is an algorithm, called a fixed-parameter 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.

Some of our algorithmic results rely on the exhaustive application of reduction rules, which are simple procedures that transform one input into another (typically smaller) input of the same problem. A reduction rule is safe if it preserves YES- and NO-instances, i.e., applying it on a YES- (NO-) instance results in a YES- (NO-) instance.




               The class  contains parameterized problems that can be solved in time  |I|^f(κ), where f is a computable function.
We say that a parameterized problem is para-hard if it remains -hard even when restricted to instances with a fixed value of the parameter.
   
     

Treewidth.
A nice tree decomposition T of a graph G = (V,E) is a pair (T, χ), where T is a tree (whose vertices are called nodes) rooted at a node t_r and χ is a function that assigns each node t a set χ(t) ⊆ V such that the following hold:

	
  * For every uv ∈ E, there is a node t such that u,v ∈χ(t).
	
  * For every vertex v ∈ V, the set of nodes t satisfying v ∈χ(t) forms a subtree of T.
	
  * |χ(ℓ)| = 0 for every leaf ℓ of T and |χ(t_r)| = 0,
	
  * There are only three kinds of non-leaf nodes in T:
	
		
  *  node: a node t with exactly one child t' such that χ(t) = χ(t') ∪v for some vertex v ∉χ(t').
		
  *  node: a node t with exactly one child t' such that χ(t) = χ(t') ∖v for some vertex v ∈χ(t').
		
  *  node: a node t with two children t_1, t_2 such that χ(t) = χ(t_1) = χ(t_2).
	


We call each set χ(t) a bag, and we use c(t) to denote the set of all vertices of G which occur in the bag of some descendant of t (possibly χ(t) itself). The width of a nice tree decomposition (T, χ) is the size of the largest bag χ(t) minus 1, and the treewidth of G is the minimum width of a nice tree decomposition of G.

Courcelle's Theorem. 
	One of the ingredients in the proof of Theorem <ref> is Courcelle's Theorem, which we introduce in this paragraph. We consider Monadic Second Order (MSO_2) logic on (edge-)labeled directed graphs in
	terms of their incidence structure, where the universe contains vertices and edges and the incidence between vertices and edges is represented by a
	binary relation. We assume an infinite supply of individual
		variables x,x_1,x_2,… and of set variables
	X,X_1,X_2,…. The atomic formulas are 
	V x (“x is a vertex”), E y (“y is an edge”), I xy (“vertex x
	is incident with edge y”), x=y (equality),
	P_a x (“vertex or edge x has label a”), and X x (“vertex or
	edge x is an element of set X”).  Formulas in MSO_2 logic are built from atomic formulas using the usual Boolean connectives
	(¬,,,→,↔), quantification over
	individual variables (∀ x, ∃ x), and quantification over
	set variables (∀ X, ∃ X).
	
	
	The free and bound variables of a formula are defined in the usual way.  	To indicate that the set of free individual variables of formula Φ
	is {x_1, …, x_ℓ} and the set of free set variables of formula Φ
	is {X_1, …, X_q} we write Φ(x_1,…, x_ℓ, X_1,
	…, X_q). If G is a digraph, v_1,…, v_ℓ∈ V(G)∪ E(G) and S_1, …, S_q
	⊆ V(G)∪ E(G) we write G Φ(v_1,…, v_ℓ, S_1, …, S_q) to denote that
	Φ holds in G if the variables x_i are interpreted by the vertices or edges v_i, for i∈ [ℓ], and the variables X_i are interpreted by the sets
	S_i, for i ∈ [q]. 
	
	The following result (the well-known Courcelle's Theorem <cit.>) 
	shows that if G has bounded treewidth then we
	can find an assignment φ to the set of free variables ℱ with G Φ(φ(ℱ)) (if one exists) in linear time.  	
	[Courcelle's Theorem <cit.>] 
		 		Let Φ(x_1,…,x_ℓ, X_1,…, X_q) be an _2 formula with free individual variables x_1,…,x_ℓ and free set variables X_1,…,X_ℓ, and let w be an integer. Then there is an algorithm 𝒜 that:
		
		
  * takes as input an n-vertex labeled directed graph G of treewidth at most w,
		
  * either outputs  v_1,…, v_ℓ∈ V(G)∪ E(G) and S_1, …, S_q	⊆ V(G)∪ E(G) such that G Φ(v_1,…, v_ℓ, S_1, …, S_q) or correctly identifies that no such vertices v_1,…, v_ℓ and sets S_1, …, S_q exist, and
		
  * runs in time f(w,|Φ(x_1,…,x_ℓ, X_1,…, X_q)|)· n for some computable function f.
		
	


        
Problem-Specific Definitions.
For a routed commodity (s,t,P) in an instance or a commodity (s,t) in an instance, we call s its source and t its destination.
For an instance (D,K,T) and v∈ V(D), we let P(v) = {(s,t,P)| (s,t,P)∈ K, P contains v} be the set of routed commodities with paths using v. 
For an instance (D',K',T') and v∈ V(D'), we overload the same notation P(v)={(s,t)| (s,t)∈ K, D' contains a directed s-t-path that passes through v} to denote the set of commodities which could be routed via v. We assume w.l.o.g. that each target is reachable from its corresponding source in the input instance (as otherwise the instance can be rejected). A graph H satisfying the conditions given in the problem statements is called a solution graph. 
   
   
We provide a simple observation on trivial YES-instances of the two problems. 
 If the target is at least the maximum outdegree of the input graph, then we are guaranteed to have a YES-instance since the input graph can be trivially used as the output graph. 
The same also holds if the target is at least the maximum number of commodities starting at any vertex, as then there is a solution by only using the edges (s,t) for all commodities (s,t) or (s,t,P).


[]


	All instances of and where the target is at least the maximum outdegree of the input graph or the maximum number of commodities starting at the same vertex are YES-instances.




§ COMPLEXITY CLASSIFICATION FROM THE PERSPECTIVE OF THE TARGET

 

Our first—and in a sense introductory—technical section is dedicated to the study of  and  when parameterized by the value of the target T. 
We begin by noting that both problems of interest are trivially solvable in linear time if T=0. 
Further, we show that these problems are para-hard when parameterized by T. 
  
    
     
         	
    
    
    
    
To show this, we reduce from the strongly problem <cit.>.


	
	m,B∈ and 3m positive integers n_1,…,n_3m such that ∑_i=1^3m n_i = mB and B/4 < n_i < B/2 for all i∈[3m].
	Can the integers n_i be partitioned into m triples such that each triple sums up to B?


In particular,  remains strongly -hard if all integers n_1,…,n_3m are distinct <cit.>. 
 

  
	and are , even when restricted to instances where T≤ 2 and D is a tree of maximum degree at most 4.	
 

We reduce from the strongly problem <cit.>, which asks: can a set of given 3m distinct positive integers n_1,…,n_3m such that ∑_i=1^3m n_i = mB be partitioned into m triples, each summing up to B? Given an instance of , we construct an instance of with T=2 as follows (for , we use the same construction and set each path to be the unique s-t-path in the constructed oriented tree). 

For D, we begin by creating a path of 2mB + 2m vertices. 
	Let S be the set of the first 2m vertices with labels s_1,s'_1,…,s_m,s'_m (in the order they appear in the path).
	The next mB vertices form the set W and are indexed by the numbers n_1,…, n_3m, specifically w_1^1,…,w_1^n_1,…,w_3m^1,…,w_3m^n_3m.
	Among the remaining mB vertices, which form the set R, there are B vertices for each triple to be created, that is, r_1^1,…,r_1^B,…,r_m^1,…, r_m^B.	
	For all i∈ [m], create the commodities (s_i,s'_i) and (s_i, r_i^j)| j∈ [B].
	For all i∈ [3m], create the commodities (w_i^j,w_i^j+1)| j∈ [n_i -1].
	For all i∈ [3m], create a vertex w̃_i, and add the edge (w_i^n_i,w̃_i) and a commodity (w_i^n_i,w̃_i).
	For all i∈ [m] and j∈ [B], create vertices r̃_i^j and r̅_i^j, and add the two edges and two commodities (r_i^j,r̃_i^j) and (r_i^j,r̅_i^j).
	The resulting graph D is depicted in <ref>. 
	
		

	
To complete the proof, it suffices to establish that the initial instance was a YES-instance if and only if so is the constructed instance.
	Intuitively, this holds since for each i∈[m] there are three available edges from s_i and s'_i that can be used to select three subpaths in the middle section, representing three integers. Each subpath w_j^1,…,w_j^n_j allows for exactly n_j outgoing edges, thus the subpaths have to be chosen such that their sum is at least B to satisfy the commodities that need to reach the last part of the path from s_i. 
The formal correctness proof, however, needs to carefully account for all possible routings for the commodities and choices of H.




	We give a reduction from with distinct positive integers to .
	The same construction holds for as well by assigning each commodity its unique path in the constructed graph.

	We construct D as follows.
	Let there be a path of 2mB + 2m vertices. 
	Let S be the set of the first 2m vertices with labels s_1,s'_1,…,s_m,s'_m (in the order they appear in the path).
	The next mB vertices form the set W and are indexed by the numbers n_1,…, n_3m, specifically w_1^1,…,w_1^n_1,…,w_3m^1,…,w_3m^n_3m.
	Among the remaining mB vertices, which form the set R, there are B vertices for each triple to be created, that is, r_1^1,…,r_1^B,…,r_m^1,…, r_m^B.	
	For all i∈ [m], create the commodities (s_i,s'_i) and (s_i, r_i^j)| j∈ [B].
	For all i∈ [3m], create the commodities (w_i^j,w_i^j+1)| j∈ [n_i -1].
	For all i∈ [3m], create a vertex w̃_i, and add the edge (w_i^n_i,w̃_i) and a commodity (w_i^n_i,w̃_i).
	For all i∈ [m] and j∈ [B], create vertices r̃_i^j and r̅_i^j, and add the two edges and two commodities (r_i^j,r̃_i^j) and (r_i^j,r̅_i^j).
	The resulting graph D is depicted in <ref>.

	

	Then the instance is a YES-instance if and only if there is a solution to in D with target 2.
	Intuitively, for each i∈[m] there are three available edges from s_i and s'_i that can be used to select three subpaths in the middle section, representing three integers. Each subpath w_j^1,…,w_j^n_j allows for n_j outgoing edges, thus the subpaths have to be chosen such that their sum is at least B to satisfy the commodities from s_i to the last part of the path.

	Formally, suppose the instance is a YES-instance. 
	For all i∈ [m], let the i^th triple in the solution be (n_⋆(i,1),n_⋆(i,2),n_⋆(i,3)).
	We define
	
    E_S    := (s_i,s'_i)| i∈[m],
    
    		E_R    := (r_i^j,r̃_i^j), (r_i^j,r̅_i^j)| i∈[m],j∈[B].
    	For all i∈ [3m] we define
    		E_W^i    := (w_i^j,w_i^j+1)| j∈ [n_i -1]∪(w_i^n_i,w̃_i),
    	and for all i∈[m] we define
    		E_C^i    := (s_i, w_⋆(i,1)^1), (s'_i, w_⋆(i,2)^1), (s'_i, w_⋆(i,3)^1),
    
    		E_R^i    := (w_⋆(i,1)^j, r_i^j) | j∈[n_⋆(i,1)]∪(w_⋆(i,2)^j, r_i^j+n_⋆(i,1)) | j∈[n_⋆(i,2)]
       ∪(w_⋆(i,3)^j, r_i^j+n_⋆(i,1)+n_⋆(i,2)) | j∈[n_⋆(i,3)].
    	Finally,
    		E_H    := E_S ∪ E_R ∪⋃_i∈ [3m] E_W^i ∪⋃_i∈ [m] E_C^i ∪⋃_i∈ [m] E_R^i.
 
	Consider the graph H with edges E_H. Then δ^+(H) = 2 as in fact δ^+(v) = 2 for each of the 2mB+2m vertices v along the main path and δ^+(v) = 0 for all other vertices.
	Observe that E_R and all E_W^i satisfy all commodities starting in vertices of R and W, respectively, and E_S satisfies all commodities with both endpoints in S.
	The remaining commodities start at the vertices s_1,…,s_m and each lead to a set of B vertices in R, such that the sets are pairwise disjoint.
	For i∈ [m], note that s_i, by also using s'_i, is connected to the first vertex of three subpaths of vertices in W, that the total length of these subpaths is exactly B, and that each of the vertices in the subpaths connects to a distinct destination required for s_i. 
	Thus, these remaining commodities are satisfied as well, and H is a solution to the instance.
	
	Now suppose there is a solution H to the instance with target 2.
	First note that for all i∈[3m] we have E_S, E_R, E_W^i ⊆ E(H), as otherwise there would be unsatisfied commodities.
	By E_R ⊆ E(H) alone, we have that each vertex in R has outdegree 2, and they can have no other edges in E(H). 
	As each t∈ R is the destination of one commodity, this implies that there have to be |R|=mB individual edges from V∖ R to R in E(H). 
	By construction of D, these edges have to start in S or W as otherwise they would not be in (D).
	Each of the mB + 2m vertices in S∪ W is allowed 2 out-edges, out of which E_S and the E_W^i already use mB + m. 
	This leaves another mB + 3m edges, out of which mB have to go to R.
	We will show below that the remaining 3m edges have to end in the first vertex in each of the 3m subpaths in W, that is, in each of w_1^1,…,w_3m^1.
	In total, the entire available outdegree of S and W is accounted for. 

	Suppose one of the 3m edges would not connect to a subpath. This would save 1 edge that can be connected to R, but now there is j∈[3m] such that there is no connection from S to any w_j^1,…,w_j^n_j. As n_j of the edges in our calculation start in w_j^1,…,w_j^n_j and can then not be used for fulfilling commodities, this would reduce the total number of available edges by n_j - 1. As n_j > B/4 and we can assume B≥ 4 (otherwise the instance becomes trivial), this reduces the amount of available edges by at least 1 and there are no longer enough edges to satisfy all commodities ending in R.
	The same issue arises when connecting to some vertex w_i^j instead of w_i^1 for some i∈[3m], j > 1.
	Hence, the remaining 3m edges end in the vertices w_1^1,…,w_3m^1.
	In particular, this implies that there are no a,b∈ [m], a≠ b such that s_a and s_b are connected to the same subpath w_j^1,…,w_j^n_j in H. 

	We now argue that s_i is connected to exactly three subpaths w_j^1,…,w_j^n_j in H and that the total length of these subpaths is B. 
	We then have a solution to where the i^th triple is n_a,n_b,n_c where s_i is (not necessarily directly) connected to w_a^1,w_b^1, and w_c^1. 
	Note that we just established that these triples are pairwise disjoint as no two vertices s_a,s_b,a≠ b connect to the same subpath.
	Consider any i∈ [m] and the remaining three outgoing edges of s_i and s'_i.
	As argued above, they either end in R or distinct vertices in W_1 = w_1^1,…,w_3m^1.
	If s_i is connected to no subpath, the three edges cannot cover all commodities of s_i.
	Thus, there is a∈ [3m] such that (s_i, w_a^1) or (s'_i,w_a^1) is in E(H).
	As this used one edge and w_a^1,…,w_a^n_a has n_a outgoing edges, we now have n_a +2 edges available. As we still assume B ≥ 4 and have n_a < B/2, this does not suffice.
	Thus, there is b∈ [3m] such that one of the n_a +2 available edges ends in w_b^1.
	Now, there are n_a + n_b + 1 edges available. 
	However, recall that n_a≠ n_b, so we have n_a + n_b -1 < B/2 + B/2 - 1 + 1 = B, so these edges still do not suffice.
	Thus, there is c∈ [3m] such that one of the n_a +n_b+1 available edges ends in w_c^1.
	This gives n_a + n_b + n_c edges available for connecting to r_i^1,…,r_i^B.
	As for all i∈ m we have that s_i is connected to at least 3 distinct vertices in W_1 and |W_1|=3m we have that there is no s_i that is connected to more than 3 vertices in W_1.
	Hence, each s_i is associated with a triple n_a,n_b,n_c, has exactly n_a+n_b+n_c edges available to connect to its B distinct destinations in R.
	Thus, for each s_i we have n_a+n_b+n_c ≥ B, and as ∑_j∈[3m] n_j = mB we have n_a + n_b + n_c = B, yielding a solution to the instance.
 


      For , we can even show hardness for T≤ 1 by a straightforward reduction from Hamiltonian Cycle.

  
	is when restricted to instances where T≤ 1.


	We reduce from Hamiltonian Cycle. 
	Let G be an undirected n-vertex graph and D be the directed graph that is obtained by replacing every edge u,v∈ E(G) by two edges (u,v) and (v,u).
	Let K = (u,v)| u,v∈ V(G), u≠ v.
	Then (D,K,1) is a YES-instance of if and only if G has a Hamiltonian cycle.
	
	Indeed, suppose G has a Hamiltonian cycle (v_1,v_2, …, v_n-1,v_n). 
	Let H be such that E(H) = (v_1,v_2), …, (v_n-1,v_n), (v_n,v_1).
	Then δ^+(H) = 1, H⊆(D), and for each pair of vertices u,v∈ V there is a directed u-v-path in H.
	On the other hand, suppose there is a solution graph H for (D,K,1). 
	As each vertex is both a source and a destination, it has at least one incoming and one outgoing edge in H.
	As δ^+(H) ≤ 1, this implies that H is a cycle cover of V. 
	Finally, as there is a commodity between each pair of vertices, V has to be a connected component in H, and so E(H) must be a Hamiltonian cycle. 
 

 



§ PARAMETERIZING BY THE NUMBER OF COMMODITIES


This section is dedicated to the study of the considered parcel sortation problems when parameterized by the number of commodities. This line of enquiry can be seen as analogous to the fundamental questions that have been investigated for other prominent examples of problems typical for logistical networks, such as the study of Vertex and Edge Disjoint Paths parameterized by the number of paths or of Coordinated Motion Planning parameterized by the number of robots. We remark that the former has been shown to be fixed-parameter tractable in Robertson and Seymour's seminal work <cit.>, while the fixed-parameter tractability of the latter has only been established on planar grid graphs in a recent work of Eiben, Ganian and Kanj <cit.>. 

We first provide a straightforward proof that instances of both and with target T ≤ 1 are in by the number of commodities (<ref>). This allows us to concentrate on the case of T≥ 2 in the rest of the section. 
        

      
	and restricted to instances such that T ≤ 1 are in when parameterized by the number of commodities.


We prove the result by showing that the problem admits a linear kernel. 
Given an instance = (D,K,1), we construct 
a reduced instance ' = (D',K,1) as follows.
	Let V(D') contain only those vertices of D which are a source or destination for at least one commodity in K. 
	Then, for all u,v∈ V(D'), let (u,v)∈ E(D') if and only if (u,v)∈ E((D)). To complete the proof, it suffices to establish correctness.




	We prove the statement by showing that there is an f(|K|)-kernel. 
	Let = (D,K,1) be an instance. 
	Create a reduced instance ' = (D',K,1) as follows.
	Let V(D') contain only the vertices in D that are the sources and destinations of the commodities in K. 
	Then, for all u,v∈ V(D'), let (u,v)∈ E(D') if and only if (u,v)∈(D).
	Clearly, this reduction is computable in polynomial time and leaves a graph with at most 2|K| vertices.
	By brute forcing the reduced instance, this kernel can then be used to obtain runtime. 
	As (D') is a subgraph of (D), any solution to ' is a solution to .
	We conclude the proof by showing that if  is a YES-instance then it has a solution that does not use any of the deleted vertices by an exchange argument.
	Let H be any solution to  and let v be a non-source, non-destination vertex in H. 
	If v has no out-neighbor in H, it does not contribute to the solution and can be removed.
	Otherwise, as H is a solution graph with outdegree 1, v has a unique out-neighbor w in H. 
	Create a new solution H' by letting V(H') = V(H)∖v, deleting the edge (v,w), and replacing each edge (u,v)∈ E(H) by an edge (u,w)∈ E(H'). 
	Then the outdegree of each vertex in H' is at most as large as its outdegree in H and thus at most 1.
	Further, the connectivity between pairs of source or destination vertices did not change. Moreover, for for every commodity routed along an s-t-path P there is still an s-t-path in H'∩(P). 
	In either case, H' is still a solution.
	By repeatedly applying this procedure, we can create a solution H' in which all non-source, non-destination vertices are removed.
 




 §.§ A Fixed-Parameter Algorithm for 

 In this subsection, we establish the fixed-parameter tractability of  under the aforementioned parameterization. Our proof relies on two main ingredients, the first of which is the generalized Ramsey's Theorem:
 
[<cit.>]

There exists a function : ×→ with the following property.
For each pair of integers r, s and each clique G of size at least (r, s) such that each edge has a single label (color) out of a set of r possible labels, it holds that H must contain a subclique H of size at least s such that every edge in H has the same label. 

In particular, we remark that  has a computable upper bound. 
  Secondly, we use the following reduction rule. 
    	
Reduction Rule R_1. 
For an instance = (D,K,T) with T ≥ 2, let U⊆ K, and q = |U|/T-1.
Suppose that there are vertices v_1, …, v_2q+2 of D such that P(v_1) = … = P(v_2q+2) = U, and for all commodities (s, t, P) ∈ U, the directed path P visits these vertices in the order of either (v_1, …, v_2q+2) or (v_2q+2, …, v_1).
Then we contract the vertices v_q+1 and v_q+2 into a vertex c and remove the outgoing edges from c to vertices other than v_1, …, v_q, v_q+3, …, v_2q+2.♢

To avoid any confusion, we explicitly remark that the vertices v_1, …, v_2q+2 need not be visited consecutively by the paths in U. An illustration of a concrete application of Reduction Rule R_1 is provided in Figure <ref> later.

  
	Reduction Rule R_1 is safe.



  Let ' = (D',K',T) be the reduced instance.
	By assumption, v_1, …, v_2q+2 are only used for the paths in U, and these paths visit these vertices in the order v_1,…, v_2q+2 (right commodities) or v_2q+2,…,v_1 (left commodities).
	Therefore, none of these vertices except for v_1 or v_2q+2 can be a source or a destination in K or K'.

	Suppose there is a solution graph H' for ' (in particular, this implies that H' is a subgraph of (D')).
We create a subgraph H of (D) from H' as follows. First, we set V(H)=(V(H')∖{c})∪{v_q+1,v_q+2}. 
For the edge set, we also begin by keeping all edges not incident to c in E(H).
 	For all (v,c)∈ E(H'), if (v,v_q+1)∈(D), let (v,v_q+1)∈ E(H). 
	Otherwise, we have (v,v_q+2)∈(D) and let (v,v_q+2)∈ E(H).
	For all (c,v)∈ E(H'), let (v_q+1,v)∈ E(H) and  (v_q+2,v)∈ E(H). 
	Note that the outdegree of c in H' and thereby the outdegree of v_q+1 and v_q+2 in H is at most T.
	Further, there is no other vertex for which the outdegree increases, as every edge to c was replaced with exactly one edge to either v_q+1 or v_q+2.
	Since the connectivity between all pairs of vertices (except c, v_q+1, and v_q+2) is the same in H and H', H is a solution to the original instance.

	Now suppose there is a solution to  by some subgraph H of (D).
	We define a U → [2q+2], where for each right (or left) commodity u=(s,t,P)∈ U we let a(u) be the smallest (or largest) integer such that s is connected to v_a(u) in H∩(P).
  	Create a subgraph H' of (D') as follows.
	Delete the vertices v_q+1 and v_q+2 with all incident edges from H and add the vertex c.
	For all v∈ V, if (v,v_q+1) or (v,v_q+2) in H, we add (v,c) to H'.
	Replace all edges (v_i,v_j) where i<j and i ≤ q or i > j and i ≥ q+3 by the edge (v_i,c).
	Now, for each right commodity u which is no longer satisfied in H', we have a(u) ≤ q+2; similarly, for each left commodity u which is no longer satisfied in H', we have a(u) ≥ q+1.
 	In both cases, the starting vertex of the commodity is connected to c in H'.
	To account for these commodities, we independently modify the outgoing edges of the vertices v_1,…,v_q+1 and v_q+2,…,v_2q+2.
	We only describe the procedure to modify the edges from v_q+2,…,v_2q+2, as the modification of the vertices v_1,…,v_q+1 follows in a symmetrical fashion.
	The goal of this procedure is to change the out-edges of v_q+2,…,v_2q+2 to satisfy all right commodities by connecting c to all targets of “unsatisfied” right commodities. 
	While doing so, we have to ensure no satisfied right commodity becomes unsatisfied and all left commodities u such that a(u) > q+2 are still connected to c.
	Intuitively, the procedure allows us to gradually route up to T-1 (or T-2) commodities directly to their destination and pass the remaining ones to the next vertex to the right. 

	Formally, for b,j ∈ [2q+2], b≤ j, let U(b,j) be the set of commodities u with b ≤ a(u) ≤ j.
	 	If there are no unsatisfied right commodities, we are done.
	Otherwise, let there be w > 0 unsatisfied right commodities.
	Identify the smallest j∈ such that j > q+2 and w ≤ (T-1) · (j-(q+2)) - |U(q+3,j)|.
	Then, iterate through i = b+1, …, j. 
	Each time, add the edge (v_i-1, v_i) (or (c, v_i) if i=q+3) and delete all outgoing edges from v_i.
	(Note that as we delete these outgoing edges, some satisfied right commodities may become unsatisfied and some left commodities u may no longer be able to reach c.)
	If there is at least one left commodity u such that a(u) = i, add the edge (v_i,c) and choose T-2 unsatisfied right commodities; if there are less, choose all.
	Otherwise, choose (up to) T-1 unsatisfied right commodities.
	 	Then, add an edge (v_i,t) for the destination t of each chosen commodity.
	Stop the procedure as soon as there are no unsatisfied right commodities left.
	 
An example of the procedure described above is provided in Figure <ref>. To complete the proof, it suffices to argue that the procedure is guaranteed to successfully terminate.
 
    




Suppose we have an instance (D,K,T), where T=2, q=3 and we consider three routed commodities with source and destination s_i,t_i, i∈ [3]. Further, suppose we have a solution graph H which contains a sequence (v_1,…,v_8) of vertices satisfying the requirements of Reduction Rule R_1, as depicted in <ref>(left), where the vertices v_q+1, v_q+2 are marked in orange.
<ref> (middle) shows the intermediate graph H' with unsatisfied commodities after v_q+1 and  v_q+2 are replaced by c.
	There, for v_q+1,v_q+2, out-edges (such as (v_4, v_1), (v_5,t_2)) are deleted and in-edges (such as (sv_6,v_5)) are replaced by edges to c.
	Edges starting before v_q+1 going right (like (v_2,v_3), (v_3,v_6)) and edges starting after v_q+2 going left are replaced by edges to c.
	<ref> (right) shows the solution graph H' after the application of the symmetrical procedures which resolve all of the three unsatisfied commodities.
	There is one unsatisfied right commodity and two commodities u such that a(u)=6. 
	Thus the smallest j guaranteeing enough outdegree in the vertices v_6,…,v_j is j=8.
	Hence, the edge (c,v_6) is added and the out-edges of v_6 are deleted, but as there is a left commodity u with a(u)=6, the edge (v_6,c) is added back in.
	The right commodity is still unsatisfied so the edge (v_6,v_7) is added back in and the edge (v_7,t_1) is used to satisfy the commodity. 
	Note that in this case (due to the left edge resolving 2 commodities at once), we break the loop before reaching v_8.
	The symmetrical procedure applied to the left hand vertices works in a similar manner, but here each vertex resolves a distinct commodity (v_1 and v_3 satisfy the left commodities and v_2 connects s_1 to c.)


     

	

	Consider the graph H' after the above procedure. 
	Note that all added edges start in the sequence (v_1, …, v_2q+2) and either end in the sequence or the destination of a commodity.
	Thus, H' remains a subgraph of (D'). 
	Further, by construction, no vertex has outdegree larger than T in H', and if the procedure terminates successfully, H' satisfies all commodities in U. 
	As all edges in E(H') ∖ E(H) have at least one endpoint in a vertex v such that P(v)=U, the commodities outside U remain unaffected by the changes.
	
	Next, we argue that the procedure is guaranteed to terminate successfully.
	To this end, we show that
	(1) during the procedure if there is an unsatisfied right commodity, then there is j, such that q+2 < j ≤ 2q+2 and w ≤ (T-1) · (j-(q+2)) - |U(q+3,j)|;
	(2) after the procedure, for any left commodity u with a(u) > q+2, there is a path in H' from a(u) to c; and
	(3) after the procedure, there is no unsatisfied right commodity u left.
	For (1), let j= 2q+2. As for all w unsatisfied commodities u, we have a(u) ≤ q+2, and hence, w + |U(q+3,j)| ≤ |U|. 
	By definition of q, we have |U| ≤ (T-1)q = (T-1)(2q+2-(q+2)).
	The statement of (1) then follows.
	To see (2), note that such a left commodity is immediately resolved by the added edge (v_i,c). 
	For (3), for a commodity u = (s,t,P), if a(u) > j, then the directed path in (P) ∩ H is still present in H', as its vertices have not been changed. 
	Thus, we only consider u such that a(u) ≤ j.
	Note that after connecting each vertex of c,v_q+3,…,v_j-1 to its successor, there are (T-1)· (j-(q+2)) available outgoing edges in the vertices v_q+3,…,v_j.
	Thus, there is one edge for each of the at most w + |U(q+3,j)| ≤ (T-1)· (j-(q+2)) commodities to resolve. 
	(To resolve a commodity u means either to create a directed path from a(u) to c if u is a left commodity or to create a directed path from a(u) to the destination of u if u is a right commodity.)
	It remains to show that at the beginning of iteration i, if there is still an unsatisfied right commodity, then we have resolved (T-1) commodities at each vertex v_j' for q+2 < j' < i.
	As j is the minimum index such that w+|U(q+3, j)| < (T-1)·(j-(q+2)), for all q+2 < j'< j we have w+ |U(q+3, j')| > (T-1)·(j'-(q+2)), and hence the vertices v_q+3,…,v_j-1 can indeed resolve (T-1) commodities each. 
	As left commodities are immediately taken care of, the only remaining commodities are right commodities which can then be satisfied by v_j.
	In summary, the procedure successfully terminates.
    As the same holds true for the symmetrical procedure, H' is a solution to I'.
  

We remark that carefully selecting a suitable interval for the symmetrical procedures is necessary and one cannot simply route commodities in a “greedy fashion” along the whole sequence. Intuitively, this is because a hypothetical solution may route the commodities in a way where they only enter the sequence at specific vertices; for instance, it may happen that many right commodities enter the sequence near its right endpoint. ()

Suppose we have a solution H to the original instance resolving four right commodities in the two rightmost vertices, as depicted in <ref>. 
Assume the target is T=2.
Though by assumption the starting vertices have to be somehow connected to the other vertices in the sequence in the underlying graph D, commodities outside the sequence might enforce that the depicted connections to the sequence are the only available ones in any solution graph.  
Thus, the two rightmost vertices have to resolve these four commodities in both the original and the reduced instance. In the standard rerouting, where each vertex on the sequence is connected to its successor, these two vertices only have a total of three available outdegree left and cannot satisfy all four commodities. 
Thus, the algorithm is designed to leave these vertices unchanged and use the other vertices in the sequence to resolve all other commodities.





We now have all the components required to establish the main result of this subsection.
 
  
	is in parameterized by the number of (routed) commodities.


The proof relies on the application of Reduction Rule R_1. However, the conditions for applying that rule are highly restrictive—in particular, identifying a sequence v_1, …, v_2q+2 of vertices satisfying the specified conditions (or even arguing that one exists) is non-trivial.
To achieve this, we begin by observing that assuming the graph is sufficiently large compared to the parameter, there must exist a large set of vertices visited by the same set of commodities. Now, we need to ensure that there exists a sufficiently long sequence such that all commodities traverse it in a “left-to-right” or “right-to-left” fashion. To find this sequence, we apply an edge labeling which intuitively captures the direction in which the routed commodities traverse the two incident vertices, and then invoke <ref>. Exhaustively applying this step allows us to reduce the instance size to a function of |K|, at which point one can solve the problem by brute force.





	Let (D, K, T) be an with |K| = k.
	When T ≤ 1, we have fixed-parameter tractability by <ref>.
	Therefore, we now assume that T ≥ 2.
	Recall the  function from <ref>.
	Let : × N → N be a computable upper bound of .
	
	For any vertex v such that P(v) = ∅, we can remove it and its incident edges from D, because no solution will use v.	
	For any nonempty subset U of K, let q = ⌈ |U| / (T - 1) ⌉.
	Let V_U be the set of vertices v such that P(v) = U.	
   	Let (s_1, t_1, P_1), …, (s_|U|, t_|U|, P_|U|) be the commodities in U.
	Define an edge-labeled complete graph on V_U, where the label of each edge is a (|U|-1)-tuple, whose i^th element is a binary number to indicate whether P_i+1 visits the incident vertices of the edge in the same or opposite order as P_1.
	(Note that when |U| = 1, there is only one label.)
	As long as |V_U| ≥(2^|U|-1,2q+2), we choose an arbitrary subset of V_U of size (2^|U|-1,2q+2), and by <ref>, we can find a subclique of size 2q+2 whose edges have the same label.
	In other words, the paths in U visit the vertices in this subclique either in the same order as P_1 does or in the reversed order.
	Then we can apply Reduction Rule R_1 to reduce the size of V_U by one.
	Repeating this procedure, we obtain an instance where 
	
    |V_U| < (2^k-1,2k+2).

	
	After processing all subsets U of K, we obtain an instance whose input graph has at most 2^k ·(2^k-1,2k+2) vertices.
	By <ref>, we can assume T is at most the maximum outdegree of the input graph.
	Therefore, the resulting instance has size bounded by a function of k and can be brute-forced in time.

	Since the reduction rule reduces the number of vertices by one, and since we apply the reduction rule after every application of <ref>, in total, we apply <ref> and the reduction rule at most |V(D)| times.
	An application of the reduction rule takes |V(D)| time. 
	To find the subclique guaranteed by <ref>, we can use a brute force approach of trying all (2q+2)-vertex subset of the vertex set of size (2^|U|-1,2q+2).
	This takes time (2^k-1,2k+2)^(2k+2).
	In total, the run time is |V(D)|^2 + |V(D)| g(k) for some computable function g. 
 



 §.§ Parameterized Algorithms for 


 We start by obtaining a reduction rule to eliminate all long paths in the input graph that is similar in spirit to the one used for , but works for unrouted commodities (<ref>). 
 This then yields an algorithm by the number of commodities (<ref>).
In the second half of the subsection, we show that is also fixed-parameter tractable under the same parameterization when restricted to planar input graphs; this is achieved via a combination of nontrivial branching, a structural result on bounded-radius planar graphs and Courcelle's Theorem (<ref>).

          
 Reduction Rule and -tractability.  We define our reduction rule for  below.
    
Reduction Rule R_2. 
For an instance = (D,K,T) with T ≥ 2, let U⊆ K, and q = |U|/T-1.
Suppose that there is a directed path (v_1, …, v_q+1) in (D) such that P(v_1) = … = P(v_q+1) = U and v_1 is neither a source nor a destination for any commodity.
Then we remove v_1 and its incident edges from D, and for every removed edge (v,v_1), we add an edge (v,v'), where v' is an out-neighbor of v_1 and either v'=v_2 or v' is on a directed path from v_1 to v_2. ♢

We note that in Reduction Rule R_2,
the edge (v, v') is added instead of (v, v_2) in order to preserve the planarity of the underlying graph D. This will be useful for obtaining <ref> later on.
The safeness of Reduction Rule R_2 can be established by building on the ideas used in the proof of <ref>.



  
	Reduction Rule R_2 is safe.


	It is easy to see that every solution to the reduced instance is a solution to the original instance.

	Suppose there is a solution to the original instance  by some subgraph H of (D).
	We now construct a solution to the reduced instance (D',K,T).
	The idea for this construction follows closely the proof of <ref>.
	We define a U → [q+1], where for each commodity u = (s,t) ∈ U we let a(u) be minimal such that there is a directed path from s to t via v_a(u) in H.
	We assume that a(u) exists for every commodity u in U; otherwise, we remove u from U.
	Create a subgraph H' of (D') as follows.
	Remove the vertex v_1 and its incident edges from H, and for every removed edge (v,v_1), add the edge (v,v_2).
	(Note that the reduction rule guarantees that (w,v_2) is still an edge in (D).)
	Because of these operations, some commodities may become unsatisfied.
	For b,j ∈ [q+1], b≤ j, let U(b,j) be the set of commodities u with b ≤ a(u) ≤ j.
	If there are no unsatisfied commodities, we are done.
	Otherwise, let w > 0 be the number of unsatisfied commodities.
	Identify the smallest j∈ such that j > 1 and w ≤ (T-1) · (j-1) - |U(2,j)|.
	Then, iterate through i = 2, …, j. 
	Each time, add an edge (v_i-1, v_i) if i > 2, and delete all outgoing edges from v_i.
	(Note that as we delete these outgoing edges, more commodities may become unsatisfied.)
	Choose T-1 unsatisfied commodities.
	Then, add an edge (v_i,t) for the destination t of each chosen commodity.
	Break the loop as soon as there are no unsatisfied commodities left.

	Consider the graph H' after the above procedure. 
	Note that all added edges start in the path (v_2, …, v_q+1) and either end at a later vertex in the path or the destination of a commodity.
	Thus, H' remains a subgraph of (D'). 
	Further, by construction, no vertex has outdegree larger than T in H', and if the procedure terminates successfully, H' satisfies all commodities in U. 
	As all edges in E(H') ∖ E(H) have at least one endpoint in a vertex v such that P(v)=U, the commodities outside U remain unaffected by the changes.
	
	What remains to be shown is that the procedure terminates successfully.
	To this end, we can use similar arguments as in the proof of <ref> to show that (1) during the procedure, if there is an unsatisfied commodity, then there is j, such that 1 < j ≤ q+1 and w ≤ (T-1)· (j-1); and (2) after the procedure, there no unsatisfied commodity left.
 

Crucially, the exhaustive application of Reduction Rule R_2 allows us to bound the length of all directed paths in D:

  
	Every instance (D,K,T) such that T≥ 2 can be reduced to an equivalent instance (D',K,T) such that all directed paths in D' have length at most 2|K|^2 in f(|K|)|V(D)|^𝒪(1) time.
	Further, for every YES-instance there is a solution graph H that is the union of paths P_1,…,P_|K|, where each P_i connects the source of the i^th commodity to its destination and has length at most 2|K|^2.


	Let |K| = k.
	For each vertex v such that P(v) = ∅, we can remove it and its incident edges from D, since no solution will use v.	
	As long as there is a directed path Q = v_1,…,v_ℓ such that ℓ > 2k^2, proceed as follows. 
	Partition Q into subsequences S_1,…,S_d such that we have P(v)=P(v') for all vertices v,v'∈ S_i, i ∈ [d].
	Note that the vertices of each subsequence S_i form a path in the transitive closure, so by exhaustively applying Reduction Rule R_2 we obtain an equivalent instance where each subsequence S_i contains at most k/T-1≤ k non-source, non-destination vertices.
	Observe that for i,j ∈ [ℓ], i< j and some commodity u ∈ K, if P(v_i) and P(v_j) both contain u, then P(v_i') also contains u for i ≤ i' ≤ j.
	Thus, along the sequence (P(v_1),…,P(v_ℓ)), each commodity is only added and removed once, giving d ≤ 2k-2.  	Thus, along the path P = v_1,…,v_ℓ, each commodity is only added and removed once, giving d ≤ 2k-2 as there are at most that many subsequences with vertices v with non-empty P(v).
	Hence, after exhaustively applying the above procedure, each directed path has length at most (2k-2)k + 2k = 2k^2 by also considering the at most 2k source or destination vertices.
	Identifying a path of length 2k^2 or showing that none exists takes (2k^2)!·|V(D)|·|E(D)| time using Monien's algorithm <cit.>.
	This time dominates the time to then apply Reduction Rule R_2. 
	This is repeated less than V(D) times as each application removes a vertex.
	Thus, the exhaustive reduction procedure takes time in k!·|V(D)|^3.

	For the second statement, note that there are only k commodities, and for each of them, all paths connecting its source and destination have length at most 2k^2.
	Consider any solution graph H and choose any s-t-path for each of the k commodities (s,t).
	Delete all vertices (including their incident edges) that are not represented in any chosen path. 
	The modified graph H is still a solution graph.
 

<ref> allows us to derive a direct  algorithm for the problem.
 

 

	is in  parameterized by the number of commodities.


	Let = (D,K,T) be an instance. If T ≤ 1, solve the instance using <ref>.
	Otherwise, by <ref>, there is a solution using at most 2|K|^3 vertices. 
	There are at most ∑_i=1^2|K|^3|V(D)|i choices of these vertices and for each choice there are less than 2^(4|K|^6) ways to connect them.
	For each setting, we can test in time f(k) for some computable function f whether it is a valid solution.


The Planar Case.
Unfortunately, we are not able to resolve the question of whether  is fixed-parameter tractable on general graphs using the tools outlined above. In particular, while <ref> intuitively allows us to view the problem as a special case of either (Induced) Subgraph Detection or Minor Detection, the former class of problems are [1]-hard on directed and undirected graphs while the latter remains elusive (and difficult to formalize) on directed graphs. Nevertheless, in this subsection we show that  is indeed fixed-parameter tractable at least when restricted to planar digraphs.

For the proof of this result, it will be useful to recall Courcelle's Theorem (<ref>) and the following relationship between treewidth and the radius of planar graphs.
 
[<cit.>]

A planar graph G with radius at most r has treewidth at most 3r+1.


It is worth noting that <ref> does not allow us to bound the treewidth of the transitive closure (D) of D; indeed, even if D is a star, (D) may easily contain large complete (bipartite) graphs. While this prevents a direct application of Courcelle's Theorem on D to solve the problem, in the following proof we show that this difficulty can be overcome by carefully branching to determine a bounded-size “template” of the solution.

  

	on planar input digraphs D is in when parameterized by the number of commodities.


	Let (D,K,T) be an instance such that T ≥ 2.
	Let k := |K| and let u_1, …, u_k be the commodities in K.
	We first apply <ref> to obtain an instance (D,K,T) where every directed path has length at most 2k^2. At this point, it is possible to show that the radius of D is at most  4k^3, which by <ref> implies that the treewidth of D is at most 12k^3+1.

<ref> further gives that there is a solution represented by the union over k paths connecting the commodities in H.
	Each s-t-path in H has an underlying s-t-path in D and this path has length at most 2k^2.
	We thus fix the sources and destinations of the commodities and branch on all f(k) possible unions D' of s_i-t_i-paths in D, for i∈[k].
	For each of these possibilities, we branch on the f'(k) possible subgraphs of their transitive closure, disregarding those that are invalid solutions by not satisfying some commodity or exceeding the target outdegree.
	It remains to decide whether any of the created graphs D' is an isomorphic subgraph of D; we resolve this final step by invoking Courcelle's Theorem <cit.>.




	Let (D,K,T) be an instance.
	If T≤ 1, by <ref>, there is a fixed-parameter algorithm to decide the instance.
	Hence, we can assume that T ≥ 2.
	Let k := |K| and let u_1, …, u_k be the commodities in K.
	We first apply <ref> to obtain an instance (D,K,T) where every directed path has length at most 2k^2.

	In order to find a solution graph in FPT-time, we first bound the treewidth of D.
	We assume D to be connected, because otherwise, we can apply our algorithm on each connected component of D independently.
	We show that the radius of D is at most 4k^3.
	Observe that for two vertices v and v' of D and some commodity (s,t) ∈ K, if (s,t)∈ P(v) ∩ P(v'), then there are directed paths from v and v' to t in D; combining these two paths yields an undirected path between v and v' of length at most 4k^2 in D. 
	Now for two arbitrary vertices v,v', since D is connected, there is a path Q from one vertex to the other in D.
	By the above observation, we can modify Q such that it is still a v-v'-path but for each commodity u∈ |K| and the subpath between the first vertex and last vertex among the vertices v_u for which u∈ P(v_u), this subpath has length at most 4k^2. 
	Thus, the length of Q is at most 4k^3, given that we deleted all vertices v_0 for which P(v_0) = ∅.
	Thereby, the radius of D is at most 4k^3.
	It is easy to see that Reduction Rule R_2 preserves planarity.
	By <ref>, we conclude that the treewidth of D is at most 12k^3+1.

	<ref> further gives that there is a solution represented by the union over k paths connecting the commodities in H.
	Each s-t-path in H has an underlying s-t-path in D and this path has length at most 2k^2.
	We thus fix the start and destination vertices of the commodities and branch on all f(k) possible unions D' of s_i-t_i-paths in D, for i∈[k].
	For each of these possibilities, we branch on the f'(k) possible subgraphs of their transitive closure, disregarding those that are invalid solutions by not satisfying some commodity or exceeding the target outdegree.
	It remains to decide whether any of the created graphs D' is an isomorphic subgraph of D.
	Let V(D') = w_1,…,w_q, q∈k^3.
	Given that D has bounded treewidth, we can decide whether D' is an isomorphic subgraph of H with respect to the fixed source and target vertices by employing Courcelle's Theorem (<ref>)
	 	 with the following MSO_2-formula of length q^2:
	
    φ(D) = ∃_v_1,…,v_q∈ V(D)∀_i,j∈ [q], i≠ j v_i ≠ v_j ∧preserveEdge(v_i,v_j) ∧preserveType(v_i).

	Here, preserveEdge(v_i,v_j) is if and only if (w_i,w_j)∉ E(D') or (v_i,v_j) in D.
	Further, preserveType(v_i) is if and only if v_i is the source/destination of the j^th commodity if and only if w_i is the source/destination of the j^th commodity. 
 



§ STRUCTURAL PARAMETERS


In our final section, we turn towards a graph-structural analysis of the considered parcel sortation problems. We note that at first glance, it may seem difficult to identify a “reasonable” graph-structural parameter that could be used to solve   or : the -hardness of both problems on an orientation of a star (<cit.> in combination with <ref>) rules out not only the use of treewidth (as by far the most widely used structural graph parameter), but also a range of other much more restrictive parameterizations such as treedepth <cit.>, the vertex cover number <cit.> and various directed variants of treewidth <cit.>. 

The above situation is not unique: there is a well-known example of another routing problem—Edge Disjoint Paths—which suffers from a similar difficulty, notably by being para-hard even on undirected graphs with vertex cover number 3 <cit.>. But for Edge Disjoint Paths, one can achieve fixed-parameter tractability when parameterizing by the combination of treewidth and the maximum degree <cit.>, while for  and  we can exclude tractability even under this combined parameterization by recalling <ref>. 

The above considerations raise the question: Are there any structural restrictions under which we can efficiently solve instances of  or  involving a large number of commodities and target? As the main contribution of this section, we answer this question positively by identifying the maximum route length as the missing ingredient required for tractability. Indeed, from an application perspective, restricting one's attention only to physical routes which do not involve too many intermediary nodes is well-aligned with practical considerations for the routing of most goods. From a formal perspective, for the purposes of this section we will assume that the parameterized instances of  and  come equipped with an additional integer parameter called path length and:


  * for , it holds that the path P of every routed commodity has length at most ;

  * for , we require that for every commodity (s,t)∈ K, there exists a directed s-t-path P' in H with a corresponding base path P in D (formally, P'⊆(P)) such that P has length at most . To formally distinguish it from , we denote this enriched problem by , and note that for ≥ |V(G)| the problems coincide.
 

As our first result, we establish the fixed-parameter tractability of both problems of 
interest when  is included in the parameterization.
  
  
	and are in by the combination of the treewidth and maximum degree of D and the path length.



We begin by computing a width-optimal nice tree-decomposition (𝚃,X) using known techniques <cit.>.
We now use the “standard” dynamic programming technique that starts at the leaves of the decomposition and traverses up to the root; however, the difficulty is that the solution graph H is only a subgraph of the transitive closure (D) and not of D itself. Therefore, a bag need not be a separator for the sought-after solution graph.
To remedy this issue, in the dynamic program we consider bounded-radius balls of vertices around each bag, and show that this ball is a separator for H, whereas the size of these balls can be upper-bounded by a function of the maximum degree and the path length. The records then essentially enumerate all possible local solutions in these balls. 

Formally, the records for a node b of 𝚃 and its corresponding ball N(b) consist of pairs (d,R) where 
d: N(b) →0, …, T and R is a directed graph over the vertices in N(b) with maximum outdegree at most T; intuitively R is the subgraph of H induced by the ball, and d stores the out-degree of vertices in the ball with respect to the hypothetical solution graph H (which may be larger than their out-degree in R since they may be incident to edges that exit the ball). More precisely, we say that a state (d,R) is included in our dynamic programming table and marked as “valid” if there is a graph H_d^R such that

	
  * H_d^R ⊆(D[c(b)∪ N(b)]);
	
  * Every vertex has outdegree at most T in H_d^R; 
	
  * For , for every (s,t) ∈ K such that s∈ c(b) or t∈ c(b), there is a directed s-t-path in H_d^R with a base path of length at most p in D and for , for every (s,t,P) ∈ K such that s∈ c(b) or t∈ c(b), there is a directed s-t-path in H_d^R∩(P);
	
  * R = H_d^R[N(b)];
	
  * Every vertex v ∈ N(b) has outdegree d(v) in H_d^R.  

To conclude the proof, one proceeds by showing how these records can be computed in a leaf-to-root fashion along (𝚃,X) and establishing correctness.





Let (D, K, T) be an or instance with path length p.
Let tw and δ_max be the treewidth and maximum degree of D, respectively.

Consider a nice tree decomposition (𝚃,X) of D with treewidth at most tw.
We use the standard dynamic programming technique that starts at the leaves of the decomposition and traverses up to the root.
  For each node b of 𝚃, let N(b) denote the set of all vertices that are in X(b) or have distance at most p in D to a vertex in X(b).
We define a state with respect to a node b as a pair (d,R) of a function d: N(b) →0, …, T and a directed graph R over the vertices in N(b) with δ^+(R) ≤ T.
We say that a state (d,R) is a candidate if there is a graph H_d^R such that

	
  * H_d^R ⊆(D[c(b)∪ N(b)]); 
	
  * Every vertex has outdegree at most T in H_d^R; 
	
  * For , for every commodity (s,t) ∈ K such that s∈ c(b) or t∈ c(b), there is a directed s-t-path in H_d^R with a base path of length at most p in D and for , for every commodity (s,t,P) ∈ K such that s∈ c(b) or t∈ c(b), there is a directed s-t-path in H_d^R∩(P);
	
  * R = H_d^R[N(b)];
	
  * Every vertex v ∈ N(b) has outdegree d(v) in H_d^R.


Clearly, if the the root r has a candidate (d,R), then H_d^R is a solution to the (D,K,T) instance.
Further, if the instance (D,K,T) is solved by some H⊆(D), the root has a candidate (d,R), where d assigns each vertex in N(b) its outdegree in H and R = H[N(b)].
Thus, identifying whether the root has a candidate suffices to decide the instance.
We use the following dynamic program to identify all candidates at each node of 𝚃.

At every node, we create a table that indicates whether a state (d,R) of the node is a candidate, defined recursively as follows.

	
  * For a leaf, the only candidate is (d,R), where d is an empty function and R the graph with V(R)=∅. 
	 	 	
  * For an  node b̅ that introduces a vertex v into a bag X(b), a state (d̅, R̅) of b̅ is a candidate if there exists a candidate (d,R) of b, such that 
	
		
  * R̅⊆(D[N(b̅)]); 
		
  * E(R̅) ∩ (N(b)× N(b)) = E(R);
		
  * For every u ∈ N(b), we have d̅(u) = d(u) + |(u,w)∈ E(R̅) | w∈  N(b̅) ∖  N(b)| ≤ T;
		
  * For every u∈ N(b̅)∖ N(b), we have d̅(u) ≤ T and d̅(u) = δ^+_R̅(u); 
		
  * For , for every (s,v)∈ K (or (v,s)∈ K) there is a directed s-v-path (v-s-path) in R̅ with a base path in D of length at most p, and for , for every (s,v,P)∈ K (or (v,s,P)∈ K) there is a directed s-v-path (v-s-path) in R̅∩(P).
	
	 	 	
  * For a  node b̅ that removes a vertex v from a bag X(b), a state (d̅, R̅) of b̅ is a candidate, if there exists a candidate (d,R) of b, such that R̅ = R[N(b̅)] and for every u ∈ N(b̅), d̅(u) = d(u).
	 	 	
  * For a  node b̅ that joins two nodes b and b', a state (d̅, R) of b̅ is a candidate, if there exist candidates (d, R) and (d', R) of b and b', respectively, such that for all
	 v ∈ N(b̅), d̅(v) = d(v) + d'(v) - δ_R^+(v) and d̅(v) ≤ T.
	

We assume δ_max > 1, because otherwise D is a union of disjoint edges, so the problem can easily be solved in linear time.
Then for each vertex v of D, N(v) is loosely bounded by δ_max^p + 1.
Consider any node b.
We have X(b) ≤ tw +1 and N(b) ≤ (tw+1)δ_max^p+1.
For every state of b, we have that d takes one of T+1 possible values for every v∈ N(b) and there are at most (∑_i=0^T+1N(b)i)^N(b) possible graphs for R. 
Therefore, the number of states of b is less than

    (T+1)^|N(b)|·(∑_i=0^T+1N(b)i)^N(b)
    	< (δ_max+1)^(tw+1)δ_max^p + 1·(∑_i=0^δ_max+1(tw+1)δ_max^p + 1i)^(tw+1)δ_max^p + 1

where by <ref>, we assume that T < δ_max.
Hence, the size of each table is bounded by some computable function f(tw, δ_max, p).
Further, we note that by the above rules computing all candidates of each node in a dynamic programming manner from the leaves to the root takes time.

We conclude the proof by noting that the above algorithm correctly identifies the candidates at each node as shown in the claim below.

 

	The algorithm correctly identifies all candidates for each node.


	We prove by induction along the tree decomposition.
	For some directed graph H and a set of vertices S⊆ V(H) we define the graph H[S]_ := (S,    E(H) ∩(D[S])); that is, it is the subgraph of H on S that only keeps edges in the transitive closure of D[S]. 

	Leaves. Here, the only candidate is the empty function and the graph with no vertices.

	 Nodes. Suppose node b̅ introduces a vertex v into a bag X(b).
	Suppose the algorithm sets (d̅, R̅) to be a candidate of b̅ as witnessed by some (d, R).
	By the induction hypothesis, (d,R) is a candidate for b witnessed by some graph H_d^R.
	We create a graph H_d̅^R̅ by combining H_d^R and R̅. In particular, V(H_d̅^R̅) = c(b̅) ∪ N(b̅) ⊇ V(H_d^R) and E(H_d̅^R̅) = E(H_d^R) ∪ E(R̅).
	Then (a) and (d) hold by construction and (b),(c), and (e) hold by combining the properties of H_d^R with the five properties of d̅ and R̅ as defined in the algorithm's  step.
	
	For the other direction, let node b̅ have a candidate (d̅, R̅) witnessed by some H_d̅^R̅. 
	Let H_d^R = H_d̅^R̅[c(b)∪ N(b)]_, d(v) = δ^+_H_d^R for every v∈ N(b), and R = H_d^R[N(b)].
	Then (d,R) is a candidate for node b as witnessed by H_d^R, where (a), (d), and (e) hold by construction, while (b) and (c) hold due to the candidate properties of H_d̅^R̅.
	In particular, for (c), we remark that all paths starting or ending in X(b) of length at most p only use vertices in N(b) and thereby do not use any of the removed edges.
	By induction, the algorithm identifies (d,R) as a candidate for node b.
	What remains to be shown is that the algorithm identifies (d,R) as a witness for (d̅,R̅) being a candidate of b̅.
	To see this, first note that R̅⊆(D[N(b̅)]) as (d̅,R̅) is a candidate. 
	By construction, E(R̅) ∩ (N(b)× N(b)) = R and, as v∈ c(R̅), condition (c) for (d̅,R̅) implies that all commodities starting or ending in v are satisfied by R̅.
	Further, (b) gives that d̅(u) ≤ T for all u∈ N(b̅) and (e) gives for all u∈ N(b̅)∖ N(b) that d̅(u) = δ^+_R̅(u) by noting that all neighbors of u are in R̅.
	Last, for vertices in N(b), by construction we have that d̅ equals d with the additional outdegree with edges to or from N(b̅)∖ N(b).
  	
	 Nodes. Suppose a node b̅ removes a vertex v from a bag X(b).
	Suppose the algorithm sets (d̅, R̅) to be a candidate of b̅ as witnessed some (d, R).
	By induction, (d,R) is a candidate for b with a respective graph H_d^R.
	Let H_d̅^R̅ = H_d^R.
	Then (b)–(e) hold by construction and (a) follows by N(b) ∖ N(b̅) ⊆ c(b), which holds as follows.
	Let u∈ N(b) ∖ N(b̅). 
	Then there is a path of length at most p from u to v that does not visit any vertices in X(b̅). Let (u',v) be the last edge of this path. Thus, by the tree decomposition, u' and v have to share some bag and as v∉ X(b̅), we have u'∈ c(b). By the same reasoning, as the path from u to u' does not pass through X(b), we have u∈ c(b).
	
	For the other direction, let node b̅ have a candidate (d̅, R̅) witnessed by some H_d̅^R̅. 
	Let H_d^R = H_d̅^R̅, for every v∈ N(b) let d(v) = δ_H_d^R^+(v), and R = H_d^R[N(b)].
	Then (d,R) is a candidate for node b as witnessed by H_d^R, where (a) holds as c(b)=c(b̅) and N(b̅) ⊆ N(b), and (b)–(e) hold by construction.
	By induction, the algorithm identifies (d,R) as a candidate for node b.
	Further, as R̅ = R[N(b̅)], the algorithm identifies (d̅,R̅) as a candidate for node b̅ as witnessed by (d,R).

	 Nodes.  Suppose a node b̅ joins two nodes b and b'.
	Suppose the algorithm sets (d̅, R) to be a candidate of b̅ as witnessed by some (d, R) and (d',R) that are, by induction, candidates of b and b', respectively.
	Let H_d^R and H_d'^R be the graphs witnessing them as candidates, respectively.
	Define H_d̅^R as their union graph.
	Conditions (a), (c), and (d) follow immediately from the candidate properties of H_d^R and H_d'^R.
	For condition (b), let v∈ c(b̅) ∪ N(b̅).
	Note that H_d^R, H_d'^R, and H_d̅^R share the induced subgraph R.
	As H_d^R and H_d'^R fulfil (b), δ_H_d̅^R^+(v) > T would imply that  Δ_H_d̅^R^+(v) ∖ N(b̅) ∩ c(b) ≠∅ and Δ_H_d̅^R^+(v) ∖ N(b̅) ∩ c(b') ≠∅. 
	In particular, v would have edges to both c(b)∖ X(b̅) and c(b')∖ X(b̅). 
	By the tree decomposition this implies v∈ X(b̅), which in turn gives that all its neighbors are in N(b̅).
	Thus there can be no such v and (b) holds.
	For condition (e), let v∈ N(b̅). 
	Note that
	Δ_H_d̅^R̅(v) ⊆  V(H_d^R) ∪ V(H_d'^R), 
	|Δ_H_d̅^R̅(v) ∩ V(H_d^R)| = d(v), and
	|Δ_H_d̅^R̅(v) ∩ V(H_d'^R)| = d'(v).
	Further, 
	Δ_H_d̅^R̅(v) ∩ V(H_d^R) ∩ V(H_d'^R) = Δ_R^+(v), as u∈ c(b) and u∈ c(b') imply u∈ X(b̅) by the tree decomposition.
	Hence, |Δ_H_d̅^R̅(v)| = d(v)+d'(v)- δ_R^+(v) and the algorithm correctly identifies (d̅, R) as a candidate.
	
	For the other direction, let node b̅ have a candidate (d̅, R) witnessed by some H_d̅^R. 
	Let H_d^R = H_d̅^R[c(b)∪ N(b̅)]_ and H_d'^R = H_d̅^R[c(b')∪ N(b̅)]_.
	Let d and d' assign every vertex in N(b̅) its outdegree in H_d^R or H_d'^R, respectively.
	Then (d,R) and (d',R) are candidates for nodes b and b', respectively, as witnessed by H_d^R and H_d'^R, where (a), (b), (d), and (e) hold by construction and (c) holds as every path of length at most p that uses a vertex in c(b) (or c(b')) cannot use a vertex outside c(b)∪ N(b̅) (or c(b)∪ N(b̅)) and no edge outside (D[c(b)∪ N(b̅)]) (or (D[c(b)∪ N(b̅)])).
	By induction, the algorithm correctly identifies (d,R) and (d',R) as candidates.
	By the same reasoning as above we have d̅(v) = |E_v| = d(v)+d'(v)- |u| (v,u)∈ E(R)| for all v∈ N(b̅), so the algorithm correctly identifies (d̅,R) as a candidate for node b̅ with (d,R) and (d',R) as witnesses.

 


Note that the constructions above can be used for a backtracking approach that allows us to reconstruct the graph H_d^R for any candidate (d,R).
Thus, the dynamic program described in the proof of <ref> can not only solve the decision problem but also output a solution H.


In the remainder of this section, we complement <ref> by showing that if any of the three parameters (treewidth, degree, and path length) is not bounded, both problems become .
<ref> in <ref> already establishes this when dealing with instances of unbounded path length. 
Van Dyk, Klause, Koenemann, and Megow <cit.> proved to be  even when the input graph is a star where every leaf has either an in- or out-edge to the center but never both.
As in such graphs, for each commodity there is a unique path connecting its source and destination, the same construction can be used for .
[<cit.>]
	
		and with path length p=2 on stars are .


Finally, we also establish -hardness even for bounded-degree digraphs where commodities have bounded path length.
 To this end, we reduce from the -complete problem, which is the restriction of  to the case where each clause has exactly three literals and each literal occurs in exactly two clauses <cit.>.

  
	is , even when restricted to instances where T ≤ 2, the path length is at most 4, and D has maximum degree at most 7.


	Suppose we have an instance of with a set C of m clauses and a set X of n variables.
	Construct D as follows.
	For every variable x∈ X, we use the variable gadget as in <ref> (left) and add the following commodities to K: (s_x, t) for t ∈t_x, t'_x, t”_x.
	For every clause c∈ C over the literals x, y, and z, we use the clause gadget as in <ref> (right). There, the vertices of x, y, and z correspond to the respective literal vertex (x or x̅) in the variable gadgets. 
	Further, we add the following commodities to K: (c, t) for t ∈x, y, z, t_c.
	We complete the proof by showing that the constructed instance with = 4 has a solution with target at most 2 if and only if the instance is a YES-instance.	
     	




	Suppose we have an instance of with a set C of m clauses and a set X of n variables.
	Construct D as follows.
	For every variable x∈ X, we use the variable gadget as in <ref> (left) and add the following commodities to K: (s_x, t) for t ∈t_x, t'_x, t”_x.
	For every clause c∈ C over the literals x, y, and z, we use the clause gadget as in <ref> (right). There, the vertices of x, y, and z correspond to the respective literal vertex (x or x̅) in the variable gadgets. 
	Further, we add the following commodities to K: (c, t) for t ∈x, y, z, t_c.
	Observe that literal vertices have the highest degree (3 in- and 4 out-edges) as they are part of one variable and two clause gadgets. 
	The constructed instance with = 4 has a solution with target at most 2 if and only if the instance is a YES-instance.

	

	Suppose we have a YES-instance of . 
	Consider the graph H such that V(H) = V(D) and
	
    E(H)    = ⋃_x∈ X E_x ∪⋃_c∈ C E_c, 
    
    		E_x    = (s_x, x̅), (s_x, t_x), (x̅,t_x'), (x̅,t_x”),   if x is ;
    (s_x, x), (s_x, t_x”), (x,t_x), (x,t_x'),   else;
    
     
    		E_c    = (c,c'), (c,x), (c',y), (c',z), (a,t_c),
 
	where a∈x,y,z is any literal in the clause. 
	Observe that H is a subgraph of (D) and for every commodity (s,t)∈ K there is a directed s-t-path in H.
	Further, the outdegree of vertices s_x, c, c' for a variable x or clause c are 2 and the outdegrees of t_x, t_x', t_x”, t_c are 0. Each literal vertex (x or x̅) that is has 2 outdegree in its variable gadget and no outdegree towards a clause gadget vertex. 
	Each literal vertex that is has no outdegree inside its variable gadget and at most outdegree 1 in each of the two clause gadgets it appears in.
	Thus, H is a solution for target 2.

	Now suppose there is a solution H for the instance with target 2.
	Consider the gadget of a variable x. 
	To fulfil all commodities inside the gadget while preserving a maximum outdegree of 2 in H, we have (x,t_x), (x,t_x')⊆ E(H) or (x̅,t_x'), (x̅,t_x”)⊆ E(H). We let x be if the first holds and x be if only the second holds.
	This variable assignment from all variable gadget satisfies all clauses as follows.
	Consider any clause c over the literals x,y,z. 
	To fulfil all commodities inside the gadget while preserving a maximum outdegree of 2 in H,
	we have (c,x), (c,c'), (c',y), (c',z)⊆ E(H).
	Then, c and c' cannot have an edge to t_c in E(H) without exceeding the target of 2.
	Thus, (a,t_c)∈ E(H) for at least one a∈x,y,z. 
	This literal has to be (and thereby satisfies the clause) because otherwise literal a would have at least outdegree 3 in H (two in its variable gadget and one in the clause gadget).
 

We modify the proof of <ref> using more sophisticated gadgets to account for the fixed paths and obtain a similar result for .

  
	is , even when restricted to instances where T ≤ 4, the path length is at most 5 and D has maximum degree at most 11.



We provide a reduction which constructs the following instance of  from an instance of .
  	For every variable x, we use the variable gadget as in <ref> (left) and add the following commodities to K: (s_x, t) for t ∈t^x_1, t^x_2, t^x_3, t^x̅_1, t^x̅_2, t^x̅_3, t^x̅_4.
	The directed paths for these commodities are exactly the unique directed paths in the gadget.
	For every clause c over the literals x,y, and z, we use the clause gadget as in <ref> (right) and add the following commodities to K. 
	First, add (a, t) for a ∈c, c', c”, c̃ and t ∈t^a_1, t^a_2.
	Second, add (c,c') and (c',c”).
	All of these commodities are assigned their unique respective path.
	Last, add (c, t) for t ∈t^c,a_1, t^c,a_2 | a ∈x, y, z. 
	For a∈x,y,z, the directed path for (c, t_1^c,a) (or (c, t_2^c,a)) is the unique directed path from c to t_1^c,a (or t_2^c,a) that contains a.
 	
	 



	Suppose we have an instance of with a set C of m clauses and a set X of n variables.
	Construct D as follows.
	For every variable x, we use the variable gadget as in <ref> (left) and add the following commodities to K: (s_x, t) for t ∈t^x_1, t^x_2, t^x_3, t^x̅_1, t^x̅_2, t^x̅_3, t^x̅_4.
	The directed paths for these commodities are exactly the unique directed paths in the gadget.
	For every clause c over the literals x,y, and z, we use the clause gadget as in <ref> (right) and add the following commodities to K. 
	First, add (a, t) for a ∈c, c', c”, c̃ and t ∈t^a_1, t^a_2.
	Second, add (c,c') and (c',c”).
	All of these commodities are assigned their unique respective path.
	Last, add (c, t) for t ∈t^c,a_1, t^c,a_2 | a ∈x, y, z. 
	For a∈x,y,z, the directed path for (c, t_1^c,a) (or (c, t_2^c,a)) is the unique directed path from c to t_1^c,a (or t_2^c,a) that contains a.
	Observe that vertices c̃ have the highest outdegree (3 in- and 8 out-edges).

	

	Suppose we have a YES-instance of . 
	Consider the graph H such that 
	
    E(H)    = ⋃_x∈ X E_x ∪⋃_c∈ C E_c,
    
    		E_x    = (s_x, x̅)∪(s_x, t_i^x) | t∈ [3]∪(x̅, t_i^x̅) | t∈ [4],
    				   if x is ;
    (s_x, x), (x,t_4^x̅)∪(x, t_i^x) | t∈ [3]∪(s_x, t_i^x̅) | t∈ [3], 
    				  else.
    
     
    		E_c    = (a, t_1^a), (a, t_2^a) | a ∈c, c', c”, c̃∪(c,c'),(c',c”),(c,c̃),(c',x), (x,t_1^c,x), (x,t_2^c,x)
       ∪(c”, t_1^c,y), (c”, t_2^c,y), (c̃,t_1^c,z), (c̃, t_2^c,z),
 
	where without loss of generality x is a literal in the clause.
	Observe that H is a subgraph of (D) and for every commodity (s,t, P)∈ K there is a directed s-t-path in H∩(P).
	Further, the outdegree of vertices t_i^x is 0 and the outdegree of vertices s_x, c, c', c”, and c̃ is 4. 
	Each literal vertex (x or x̅) that is has 4 outdegree in E_x and no outdegree in any E_c.
	Each literal vertex that is has no outdegree in E_x and at most outdegree 2 in each of E_c, E_c', the two clause gadgets it appears in.
	Thus, H is a solution for target 4.

	Now suppose there is a solution H for the instance with target 4.
	Consider the gadget of a variable x and partition the vertices in two sets S_x = (s_x, x, x̅) and T_x = t_1^x,t_2^x,t_3^x,t_1^x̅,t_2^x̅,t_3^x̅,t_4^x̅.
	We let x be if and only if there are at most 2 edges (x,t)∈ H such that t∈ T_x ∪{x̅}.
	Note that in this case there are more than 2 edges (x̅,t)∈ H such that t∈ T_x as otherwise not all commodities in the gadget would be satisfied.
	This variable assignment from all variable gadget satisfies all clauses as follows.
	Consider any clause c over the literals x,y,z. 
	To fulfil all commodities inside the gadget,
	we have (a, t_1^a), (a, t_2^a) | a ∈c, c', c”, c̃⊆ E(H) as well as (c,c'),(c',c”)∈ E(H).
	This already gives c and c' an outdegree of 3 and c” an outdegree of 2.
	Thus, there can be at most 4 more edges starting in S_x to satisfy the 6 remaining commodities (c,t), t∈ T_x.
	We can use one of the 4 edges to connect to c̃, which still has capacity for 2 not yet accounted edges. 
	Still one of the 6 remaining commodities is unsatisfied, for which the only remaining option is to use the vertices x,y, or z.
	Suppose all literals in the clause were . 
	Then, in particular, x,y,z have already used at least 3 of their 4 out-edges towards vertices in their respective variable gadget.
	As connecting c to any of x,y, or z takes one edge each and only enables at most one edge each, it is not possible to satisfy all 6 remaining commodities.
	Therefore, at least one of x,y, or z uses at most 2 edges in its variable gadget, and therefore, it is and satisfies the clause.
 





§ CONCLUDING REMARKS AND DISCUSSION

We studied the complexity landscapes for the studied formalizations of the higher-level and lower-level parcel sortation problems. While our results provide an extensive parameterized classification, it remains unclear whether 
admits a fixed-parameter algorithm w.r.t. the number of commodities |K| (without the restriction to planar graphs). 

   
This question turns out to be connected to the long-standing research efforts in the area of directed minor checking, where we lack a rigid definition of the minor relationship on directed graphs (as opposed to the well-established non-uniform minor-testing machinery on undirected graphs <cit.>). Indeed, as a subgraph of the transitive closure of D, H can in some respects be expected to occur as a “directed minor” of D. Moreover, since the size of H in a hypothetical solution can be bounded due to <ref> and since we may exhaustively branch on the structure of H, a fixed-parameter “directed minor” testing procedure would likely allow us to test for H and thus establish fixed-parameter tractability of the problem. In this sense, settling our specific open question may potentially lead to more generally applicable insights in the area of directed minors. 

It is also worth noting that the complexity-theoretic behavior of both and w.r.t. graph-structural parameterizations is somewhat unique: there seem to exist no structural parameterizations of D alone which would yield  or fixed-parameter algorithms without bounding the input size. 
 Indeed, it is only through the addition of the path length as a parameter that we can achieve tractability in <ref>. Luckily, this parameter is well-motivated, as in practice virtually all commodities are routed via rather short paths in the fulfillment network due to its hierarchical nature. We further remark that the proof of <ref> immediately also yields fixed-parameter tractability of w.r.t. the treewidth of D plus the number of commodities.
 Finally, one may also aim to settle the classical complexity of the baseline case of  when T=1.



    Acknowledgments.
 The authors acknowledge support from the Austrian Science Fund (FWF, Project Y1329).

                      

   
 


  
 

