Complexity of moving labeled tokens on graphs remains high on trees and grids
On the complexity of the single-move labeled token routing problem
Computational ComplexityDiscrete MathematicsData Structures and AlgorithmsRobotics
Summary
This paper studies a problem where tokens with labels must be routed from start positions to targets on a graph with certain compatibility rules and without collisions. The authors find that deciding if such movements exist is computationally difficult—even on simple structures like trees and grid graphs, and even under restrictive conditions like few shared route edges. They also identify specific graph properties that influence how hard the problem is, and when it might be easier to solve. This work helps understand limitations of organizing movements in systems like neutral-atom quantum computers.
What this means in practice
- •For quantum hardware engineers: Help predict computational limits when planning atom movements in neutral-atom quantum computers that need labeled routing with compatibility constraints.
- •For robotics path planners: Inform design decisions about moving multiple labeled robots on networks without collisions when each robot has limited target options.
A theory result. No direct application yet.
Authors
Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad, Naomi Nishimura
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 $\mathsf{NP}$-complete on grid graphs when each source is compatible with exactly one target. We prove that the latter case remains $\mathsf{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 $\mathsf{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 $\mathsf{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 $\mathsf{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 $\mathsf{P}=\mathsf{NP}$, neither the maximum degree nor the candidate edge multiplicity can be omitted.