  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.
  We perform a thorough parameterized analysis of the complexity of both
problems. Our results concentrate on three fundamental parameterizations of the
problem: (1) When attempting to parameterize by the target outdegree of H, we
show that the problems are paraNP-hard even in highly restricted cases; (2)
When parameterizing by the number of commodities, we utilize Ramsey-type
arguments, kernelization and treewidth reduction techniques to obtain
parameterized algorithms for both problems; (3) 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 paraNP-hardness.
