Parameterized Complexity of Vehicle Routing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909002234855424 |
|---|---|
| author | Döring, Michelle Fehse, Jan Friedrich, Tobias Marten, Paula Mohrin, Niklas Simonov, Kirill Soheil, Farehe Timm, Jakob Verma, Shaily |
| author_facet | Döring, Michelle Fehse, Jan Friedrich, Tobias Marten, Paula Mohrin, Niklas Simonov, Kirill Soheil, Farehe Timm, Jakob Verma, Shaily |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10361 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parameterized Complexity of Vehicle Routing Döring, Michelle Fehse, Jan Friedrich, Tobias Marten, Paula Mohrin, Niklas Simonov, Kirill Soheil, Farehe Timm, Jakob Verma, Shaily Computational Complexity Data Structures and Algorithms 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. |
| title | Parameterized Complexity of Vehicle Routing |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.10361 |