On the complexity of the single-move labeled token routing problem
Abstract
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom. Motivated by this task, we introduce Single-Move Labeled Token Routing: every source and every target vertex of a graph is assigned a set of labels, and tokens occupy the sources. A solution consists of a matching that assigns each source to a compatible target (one whose label set intersects its own), a route for each matched pair, and a movement order in which, when a token is moved, its route contains no other token. The problem is known to be polynomial-time solvable when every source is compatible with every target, and NP-complete on grid graphs when each source is compatible with exactly one target. We prove that the latter case remains NP-complete on grids and on planar graphs of maximum degree four even when some solution has pairwise edge-disjoint routes. On trees, the problem is known to be NP-complete even for maximum degree three. We study trees through the solution edge multiplicity, the largest number of routes of a solution sharing an edge, and the candidate edge multiplicity, the largest number of compatible pairs whose paths share an edge. We prove that on trees of maximum degree three, the problem is W[1]-hard parameterized by a bound on the solution edge multiplicity, even when a movement order is given, and that on trees of unbounded degree, it is NP-complete even when the candidate edge multiplicity is at most eight. We show that on trees the problem is fixed-parameter tractable parameterized by the maximum degree together with the candidate edge multiplicity, and also by the candidate vertex multiplicity, the same count at vertices. Unless P=NP, neither the maximum degree nor the candidate edge multiplicity can be omitted.
Related
- On the T-Adaptive Segment Routing Problem
- RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
- Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
- Carbon-Aware Electric Vehicle Routing Problem with Decision-Focused Learning
- An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
BibTeX
@misc{bousquet2026complexity,
title = {{On the complexity of the single-move labeled token routing problem}},
author = {Nicolas Bousquet and Remy El Sabeh and Amer E. Mouawad and Naomi Nishimura},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09084},
eprint = {2610.09084},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09084},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the complexity of the single-move labeled token routing problem
AU - Nicolas Bousquet
AU - Remy El Sabeh
AU - Amer E. Mouawad
AU - Naomi Nishimura
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09084
UR - https://arxiv.org/abs/2610.09084
AB - In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom. Motivated by this task, we introduce Single-Move Labeled Token Routing: every source and every target vertex of a graph is assigned a set of labels, and tokens occupy the sources. A solution consists of a matching that assigns each source to a compatible target (one whose label set intersects its own), a route for each matched pair, and a movement order in which, when a token is moved, its route contains no other token. The problem is known to be polynomial-time solvable when every source is compatible with every target, and NP-complete on grid graphs when each source is compatible with exactly one target. We prove that the latter case remains NP-complete on grids and on planar graphs of maximum degree four even when some solution has pairwise edge-disjoint routes. On trees, the problem is known to be NP-complete even for maximum degree three. We study trees through the solution edge multiplicity, the largest number of routes of a solution sharing an edge, and the candidate edge multiplicity, the largest number of compatible pairs whose paths share an edge. We prove that on trees of maximum degree three, the problem is W[1]-hard parameterized by a bound on the solution edge multiplicity, even when a movement order is given, and that on trees of unbounded degree, it is NP-complete even when the candidate edge multiplicity is at most eight. We show that on trees the problem is fixed-parameter tractable parameterized by the maximum degree together with the candidate edge multiplicity, and also by the candidate vertex multiplicity, the same count at vertices. Unless P=NP, neither the maximum degree nor the candidate edge multiplicity can be omitted.
ER -