2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27454 2026-08-21T14:42:40Z ddc:004 open_access

Parameterized Complexity of Efficient Sortation Ganian, Robert Hoang, Hung P. Wietheger, Simon sort point problem parameterized complexity treewidth 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 fixed or can be chosen arbitrarily. We perform a thorough parameterized analysis of the complexity of both problems, concentrating on three fundamental parameterizations: 1) When considering 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 and the color-coding technique to obtain fixed-parameter algorithms for both problems; 3) When parameterizing by the structure of D, we establish fixed-parameter tractability for both problems w.r.t. the combined parameterization of treewidth, maximum degree and the maximum routing length. We complement this with lower bounds which show that omitting any of the three parameters results in paraNP-hardness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Ganian and Hung P. Hoang and Simon Wietheger 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.72 urn:nbn:de:0030-drops-274548 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.72 eng https://creativecommons.org/licenses/by/4.0/legalcode