pith. sign in

arxiv: 2509.10361 · v1 · submitted 2025-09-12 · 💻 cs.CC · cs.DS

Parameterized Complexity of Vehicle Routing

Michelle D\"oring , Jan Fehse , Tobias Friedrich , Paula Marten , Niklas Mohrin , Kirill Simonov , Farehe Soheil , Jakob Timm
show 1 more author
Shaily Verma
This is my paper

Pith reviewed 2026-05-18 17:50 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords vehicle routingparameterized complexitytreewidthFPT algorithmW-hardnesscapacitated vehicle routingXP algorithm
0
0 comments X

The pith

Vehicle routing without capacity limits can be solved efficiently on graphs with small treewidth, while capacitated versions are hard for the same parameter.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that the basic vehicle routing problem admits an efficient algorithm when the underlying graph has small treewidth. If this holds, then routing tasks on tree-like networks become practical even with many vehicles. Adding capacity limits on what each vehicle can carry changes the picture, leading to hardness results that rule out similarly efficient algorithms. Combining treewidth with a bound on capacity yields a slower but still parameterized algorithm. A reader would care because this separates tractable and intractable variants for real-world networks that often have low treewidth.

Core claim

We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[·]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.

What carries the argument

Dynamic programming over tree decompositions of the graph for the uncapacitated case, paired with hardness reductions that incorporate capacity limits.

If this is right

  • VRP admits an algorithm running in f(treewidth) times polynomial time in the graph size.
  • CVRP is unlikely to admit any FPT algorithm when parameterized only by treewidth.
  • CVRP admits an XP algorithm running in n to the power of g(treewidth plus capacity) for some function g.
  • Similar hardness holds for other listed parameterizations of CVRP such as number of depots or number of vehicles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Capacity limits appear to introduce a source of complexity that cannot be tamed by graph structure alone.
  • Algorithm designers might prioritize exact solutions for uncapacitated routing on low-treewidth inputs while using heuristics for capacitated cases.
  • Related problems with resource bounds, such as delivery with load limits, may exhibit the same hardness pattern on tree-like graphs.

Load-bearing premise

The input is an undirected weighted graph with a set of depots and clients where each route must start and end at a depot and all clients must be covered.

What would settle it

A graph family with bounded treewidth where capacitated vehicle routing requires more than polynomial time in the number of clients for any fixed small capacity value.

read the original abstract

The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph $G$, there are $k$ vehicles available to jointly cover the set of clients $C \subseteq V(G)$. Every vehicle must start at one of the depot vertices $D \subseteq V(G)$ and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of $G$. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and $W[\cdot]$-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims an FPT algorithm for the (uncapacitated) Vehicle Routing Problem parameterized by treewidth of the input undirected weighted graph, via dynamic programming on tree decompositions that tracks configurations of open routes and computes the minimum number of vehicles. For the three variants of Capacitated Vehicle Routing (CVRP), it proves paraNP-hardness and W[·]-hardness for parameterizations including treewidth (via reductions encoding capacity constraints), rendering FPT algorithms unlikely, while providing an XP algorithm for the joint parameterization by treewidth and vehicle capacity.

Significance. If the results hold, the work provides a precise map of the parameterized complexity boundary between VRP and CVRP. The FPT result for VRP demonstrates that standard treewidth DP techniques extend to routing with multiple depots and return-to-start constraints without extra factors from the number of vehicles. The hardness results for CVRP variants isolate capacity as the source of intractability even on bounded-treewidth graphs, while the XP algorithm supplies a concrete baseline when capacity is treated as a second parameter. Explicit modeling of the input as an undirected graph with distinguished depots D and clients C, together with the requirement that routes jointly cover all clients and return to their starts, strengthens the applicability of the claims to standard VRP formulations in logistics.

major comments (2)
  1. [§4] §4 (FPT algorithm for VRP by treewidth): the state description for tracking open routes in the DP must explicitly bound the number of partial routes per bag by a function of treewidth alone; if the number of depots or vehicles enters the state space, the claimed FPT runtime is no longer guaranteed.
  2. [§5] §5 (hardness for CVRP by treewidth): the reduction establishing W[1]-hardness (or paraNP-hardness) must be checked for correctness on the capacity encoding; if the reduction introduces an exponential blow-up in the number of clients or depots relative to the parameter, it fails to separate the hardness from the treewidth parameter.
minor comments (2)
  1. [Abstract] Abstract: the notation 'W[·]-hardness' is imprecise; replace with the specific class (e.g., W[1]-hardness) or clarify the exact parameterized class intended.
  2. [Problem definition] Problem definition (early section): the distinction between the three CVRP variants (client-capacity, distance-capacity, or both) should be stated with explicit formal constraints rather than left to the informal description.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We address the major comments point by point below. We believe the results hold as stated but will revise the manuscript to improve clarity on the points raised.

read point-by-point responses

  1. Referee: [§4] §4 (FPT algorithm for VRP by treewidth): the state description for tracking open routes in the DP must explicitly bound the number of partial routes per bag by a function of treewidth alone; if the number of depots or vehicles enters the state space, the claimed FPT runtime is no longer guaranteed.

    Authors: We appreciate this observation. In our dynamic programming approach, the states for each bag are configurations of partial routes whose open endpoints lie within the bag. Since the bag size is bounded by tw + 1, the possible configurations correspond to the ways to match or partition a subset of these vertices into paths (representing open routes). The number of such configurations is at most the number of partial matchings on tw + 1 elements, which is bounded by a function of tw alone (specifically, at most 2^{O(tw log tw)} or tighter bounds via known enumeration of matchings). Importantly, we do not include the identities of specific depots or the total number of vehicles in the per-bag state; instead, the minimum number of vehicles is computed as part of the DP value, and depots are accounted for when a route is initiated or closed at a depot vertex during the traversal of the tree decomposition. This ensures the overall runtime remains FPT in tw. We will revise §4 to include an explicit statement bounding the state space size by a function of treewidth. revision: yes

  2. Referee: [§5] §5 (hardness for CVRP by treewidth): the reduction establishing W[1]-hardness (or paraNP-hardness) must be checked for correctness on the capacity encoding; if the reduction introduces an exponential blow-up in the number of clients or depots relative to the parameter, it fails to separate the hardness from the treewidth parameter.

    Authors: Thank you for raising this point. Our hardness reductions for the CVRP variants are designed to preserve the treewidth up to a function of the original parameter. Specifically, the reductions are from W[1]-hard problems such as Clique parameterized by solution size k, and the constructed graph has treewidth O(k) while the number of clients and depots is polynomial in the size of the original instance, with no exponential dependence on k. The capacity constraints are encoded using additional structures (such as paths or gadgets) whose size is linear in the original parameters, ensuring the treewidth bound holds. We have verified that the capacity encoding does not cause an exponential blow-up. To make this explicit, we will add a short paragraph or lemma in §5 detailing the treewidth of the reduced instance. revision: partial

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes an FPT algorithm for VRP by treewidth via dynamic programming on tree decompositions that tracks open routes and vehicle counts, paraNP- and W-hardness for CVRP variants by treewidth through explicit reductions encoding capacity, and an XP algorithm for the joint treewidth-plus-capacity parameterization. These follow standard parameterized complexity techniques applied directly to the explicitly defined input model (undirected weighted graph with depots D and clients C, routes starting and ending at depots). No self-definitional constructs, fitted parameters renamed as predictions, or load-bearing self-citations appear; the results are derived from the problem statement and conventional algorithmic/hardness methods without reducing to their own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard definitions of treewidth, FPT, XP, paraNP-hardness, and W-hardness from parameterized complexity theory. No free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Treewidth is a well-defined graph parameter that admits dynamic programming on tree decompositions.
    Invoked implicitly when claiming FPT and XP algorithms parameterized by treewidth.
  • standard math Standard notions of FPT, XP, paraNP-hardness, and W[·]-hardness classify parameterized problems.
    Used to state the algorithmic and hardness results.

pith-pipeline@v0.9.0 · 5744 in / 1388 out tokens · 40473 ms · 2026-05-18T17:50:05.879658+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Walking through waypoints

    Saeed Akhoondian Amiri, Klaus-Tycho Foerster, and Stefan Schmid. Walking through waypoints. Algorithmica , 82(7):1784--1812, 2020

    work page 2020

  2. [2]

    Complexity of finding embeddings in a k-tree

    Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods , 8(2):277--284, 1987

    work page 1987

  3. [3]

    Fomin, Petr A

    Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, William Lochet, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Kirill Simonov. Packing short cycles. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 1...

    work page doi:10.1137/1.9781611978322.45 2025

  4. [4]

    Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

    Hans L Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation , 243:86--111, 2015

    work page 2015

  5. [5]

    The vehicle routing problem: State of the art classification and review

    Kris Braekers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers & industrial engineering , 99:300--313, 2016

    work page 2016

  6. [6]

    Parameterized algorithms , volume 5

    Marek Cygan, Fedor V Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized algorithms , volume 5. Springer, 2015

    work page 2015

  7. [7]

    G. B. Dantzig and J. H. Ramser. The truck dispatching problem. Management Science , 6:80--91, 10 1959

    work page 1959

  8. [8]

    Bodlaender, S\' a ndor Kisfaludi-Bak, and Sudeshna Kolay

    Mark de Berg, Hans L. Bodlaender, S\' a ndor Kisfaludi-Bak, and Sudeshna Kolay. An eth-tight exact algorithm for euclidean tsp. SIAM Journal on Computing , 52(3):740--760, 2023. https://arxiv.org/abs/https://doi.org/10.1137/22M1469122 arXiv:https://doi.org/10.1137/22M1469122 , https://doi.org/10.1137/22M1469122 doi:10.1137/22M1469122

    work page doi:10.1137/22m1469122 2023

  9. [9]

    An application of simultaneous diophantine approximation in combinatorial optimization

    Andr \'a s Frank and \'E va Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica , 7:49--65, 1987

    work page 1987

  10. [10]

    Computers and intractability , volume 174

    Michael R Garey and David S Johnson. Computers and intractability , volume 174. freeman San Francisco, 1979

    work page 1979

  11. [11]

    Bin packing with fixed number of bins revisited

    Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences , 79(1):39--49, 2013. URL: https://www.sciencedirect.com/science/article/pii/S0022000012000943, https://doi.org/10.1016/j.jcss.2012.04.004 doi:10.1016/j.jcss.2012.04.004

    work page doi:10.1016/j.jcss.2012.04.004 2013

  12. [12]

    Minkowski's convex body theorem and integer programming

    Ravi Kannan. Minkowski's convex body theorem and integer programming. Mathematics of operations research , 12(3):415--440, 1987

    work page 1987

  13. [13]

    A single-exponential time 2-approximation algorithm for treewidth

    Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. SIAM Journal on Computing , 0(0):FOCS21--174--FOCS21--194, 2023. https://arxiv.org/abs/https://doi.org/10.1137/22M147551X arXiv:https://doi.org/10.1137/22M147551X , https://doi.org/10.1137/22M147551X doi:10.1137/22M147551X

    work page doi:10.1137/22m147551x 2023

  14. [14]

    Integer programming with a fixed number of variables

    Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of operations research , 8(4):538--548, 1983

    work page 1983

  15. [15]

    Vehicle routing problems over time: a survey

    Andrea Mor and Maria Grazia Speranza. Vehicle routing problems over time: a survey. Annals of Operations Research , 314(1):255--275, 2022

    work page 2022

  16. [16]

    On the capacitated vehicle routing problem

    Ted K Ralphs, Leonid Kopman, William R Pulleyblank, and Leslie E Trotter. On the capacitated vehicle routing problem. Mathematical programming , 94:343--359, 2003

    work page 2003

  17. [17]

    Graph minors

    Neil Robertson and Paul D Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B , 36(1):49--64, 1984

    work page 1984

  18. [18]

    Waypoint routing on bounded treewidth graphs

    S imon Schierreich and Ond r ej Such\' y . Waypoint routing on bounded treewidth graphs. Information Processing Letters , 173:106165, 2022. URL: https://www.sciencedirect.com/science/article/pii/S0020019021000806, https://doi.org/10.1016/j.ipl.2021.106165 doi:10.1016/j.ipl.2021.106165

    work page doi:10.1016/j.ipl.2021.106165 2022