On the complexity of the single-move labeled token routing problem

Nicolas Bousquet; Remy El Sabeh; Amer E. Mouawad; Naomi Nishimura

cs.CCOct 6, 2026

On the complexity of the single-move labeled token routing problem

Authors: Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad, Naomi Nishimura

Organizations: American University of Beirut, Beirut, Lebanon

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.

Figures & tables

Figure 1: The expansion of an ordinary vertex

u

of degree at least four. On the left,

u

has five neighbors

v_{1},\ldots,v_{5}

, and the edge

uv_{i}

crosses the boundary of the dashed disc around

u

at the point

p_{i}

. On the right, the part of the drawing inside the disc is replaced by a tree

F_{u}

of maximum degree three, whose leaves lie at the points

p_{1},\ldots,p_{5}

, and the leaf at

p_{i}

is joined to

v_{i}

by the part of

uv_{i}

outside the disc; for readability, the disc is enlarged on the right and the rest of the drawing is stretched accordingly. None of the vertices of

F_{u}

is a source or a target. Dotted edge segments indicate that the graph continues beyond the neighbors of

u

: the rest of the graph, which the expansion leaves unchanged, is not drawn.

Figure 2: A rectilinear representation of the Planar Monotone Rectilinear 3-SAT instance

\varphi=(x_{1}\lor x_{2}\lor x_{4})\land(x_{2}\lor x_{3})\land(\overline{x}_{1}\lor\overline{x}_{2})\land(\overline{x}_{2}\lor\overline{x}_{3}\lor\overline{x}_{4})\land(\overline{x}_{1}\lor\overline{x}_{4})

. The positive clauses are drawn above the variable line, and the negative clauses below it. A clause box is joined by a vertical segment to each of its variables, so one clause may reach several variables.

Figure 3: Part of the construction for the positive clause

C=x_{1}\lor x_{2}\lor x_{4}

\varphi

(Figure 2 ); for

i\in\{1,2,4\}

a_{i}

and

g_{i}

denote the assignment token and the junction of the gadget of

x_{i}

, and

b_{i}

and

d_{i}

the blocking and delay tokens of the occurrence of

x_{i}

C

. In every variable gadget, the true path is drawn above and the false path below. The dotted rectangles single out the gadget of

x_{2}

and the gadget of

C

. The blue dash-dotted curves and the orange dashed curves are the occurrence edges of the blocking tokens and of the delay tokens, respectively. The occurrence edges of other clauses are omitted, but the sources and targets that those clauses create on the true and false paths are shown.

Figure 4: The graph

G_{\mathrm{pl}}

for the formula of Figure 2 , drawn as in the proof of Lemma 18 and restricted to the four variable gadgets and to the clause gadgets of

(x_{1}\lor x_{2}\lor x_{4})

(x_{2}\lor x_{3})

, and

(\overline{x}_{2}\lor\overline{x}_{3}\lor\overline{x}_{4})

; the gadgets of the other two clauses, their occurrence edges, and the vertices that their occurrences add to the variable gadgets are omitted. The dotted rectangles are the boxes of

\mathcal{R}

, and the dash-dotted blue curves and dashed orange curves are the occurrence edges of the blocking tokens and of the delay tokens, as in Figure 3 . In the box of the clause

C=x_{1}\lor x_{2}\lor x_{4}

, whose occurrences

o_{1}

o_{2}

, and

o_{3}

are those in

x_{1}

x_{2}

, and

x_{4}

, the vertices are labeled with the tokens indexed by occurrence, and so are the sources

\mathrm{s}(b_{i})

and targets

\mathrm{t}(d_{i})

of its occurrence edges in the boxes of

x_{1}

x_{2}

, and

x_{4}

;

u_{C}

is the crossing vertex of

C

, at which the occurrence edge of

b_{2}

ends. In each variable gadget, the false path, which carries the vertices of the positive occurrences, is drawn above the variable line and the true path below it, whereas Figure 3 draws the true path above.

Figure 5: The arrangement of the choice subtrees, the tile subtree, the two storage paths, and the cleanup path in the instance constructed from a Grid Tiling instance.

Figure 6: The movement order associated with a fixed cell

(i,j)

, assuming that the value

a_{i}

is chosen for row

i

and the value

b_{j}

for column

j

. The numbers in parentheses identify the order in which the moves are to be executed, and their positions indicate the source and the target of that move. The label sets of the indicated sources and targets are displayed inside rectangles. Ellipses represent portions of the construction not relevant to the depicted moves: the gadgets retain their relative positions from Figure 5 .

Figure 7: Part of the construction of Theorem 5 : the variable gadget for a variable

x

with occurrences

o_{1}

o_{2}

, and

o_{3}

, of which

o_{1}

is positive and lies in the clause

C

while

o_{2}

and

o_{3}

are negative and lie in two other clauses, and the clause gadget for

C

, whose occurrences are

o_{1}

o_{4}

, and

o_{5}

. A dashed enclosure surrounds the sources and targets that carry one shared label, and a vertex inside two enclosures carries both. The two arrows mark the two tokens of

o_{1}

that move between the gadgets.

Figure 8: One combination step at a vertex

v

with children

u

and

w

, described in the text. The route of each pair of the matching is drawn beside the tree edges it uses; as the legend shows, its color and dash pattern indicate whether the pair crosses

e_{v}

, stops at a child boundary, or stays inside

G_{u}

. Below the tree, the entries chosen at

u

and

w

are listed under

G_{u}

and

G_{w}

, the left panel shows the digraph

D

, and the right panel shows the entry produced at

v

; the dashed arrow is the order

p_{4}\prec p_{1}

Explore similar work

Jun 4, 2026cs.RO

Hardness of Multi-Agent Path Finding on Trees: A Unified Approach

This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives - distance, makespan, and flowtime - for both labeled and colored variants. In MAPF, agents occupy the vertices of a graph and must move to target vertices without collisions while optimizing a given objective. In the labeled case, the agents are distinct and have respective targets; in the colored case, agents of the same color are interchangeable. While many MAPF variants are known to be intractable, several basic cases on trees have remained open. We prove NP-hardness on trees for both labeled and 2-colored MAPF under all three objectives. In particular, we resolve the classical Pebble Motion problem, where one pebble moves at a time to an adjacent empty vertex and the goal is to minimize the total number of moves. Despite being one of the most basic discrete motion models, its complexity on trees had remained open for several decades. Moreover, for colored Pebble Motion, we give the first hardness result on any graph class, already with two colors, which is tight. All of these results are established through the hardness of Stack Rearrangement, itself posed as an open problem, which asks to optimally rearrange items stored in stacks, and which we also prove to be NP-hard. Notably, the connection to stacks yields hardness already on very simple trees - subdivided stars - across all problems. Together, these results reveal a common tractability barrier that permeates several fundamental motion models, thereby unifying and strengthening prior hardness results.

Tzvika Geft

Rutgers University, NJ, USA · NJ, USA

Multi-Agent Path Finding Np-Hard Motion Model Hard Motion Trees

Ask PDF

May 12, 2026quant-ph

QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning

Qubit routing is a fundamental problem in quantum compilation, known to be NP-hard. Its dynamic nature makes local routing decisions propagate and compound over time, making global efficient solutions challenging. Existing heuristic methods rely on local rules with limited lookahead, while recent learning-based approaches often treat routing as a generic sequential decision problem without fully exploiting its underlying structure. In this paper, we introduce QAP-Router, framing qubit routing based on a dynamic Quadratic Assignment Problem (QAP) formulation. By modeling logical interactions, or quantum gates, as flow matrices and hardware topology as a distance matrix, our approach captures the interaction-distance coupling in a unified objective, which defines the reward in the reinforcement learning environment. To further exploit this structure, the policy network employs a solution-aware Transformer backbone that encodes the interaction between the flow matrix and the distance matrix into the attention mechanism. We also integrate a lookahead mechanism that blends naturally into the QAP framework, preventing myopic decisions. Extensive experiments on 1,831 real-world quantum circuits from the MQTBench, AgentQ and QUEKO datasets show that our method substantially reduces the CNOT gate count of routed circuits by 15.7%, 30.4% and 12.1%, respectively, relative to existing industry compilers.

Kien X. Nguyen, Ankit Kulshrestha, Ilya Safro +1

Department of Computer and Information Sciences, University of Delaware, USA · Quantum Lab, Fujitsu Research of America, USA

Quantum Circuits Qubit Repair-Assignment Problem Lookahead

Ask PDF

Jul 26, 2026cs.CC

Maximum Satisfiability of Simple Temporal Problems

The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables

n

(instance scale), the maximum coefficient magnitude

k

(numeric range), and structural parameters of the constraint graph such as treewidth

tw

(decomposability) and vertex cover size

vc

(density). We show that MAXSTP is W[1]-hard parameterized by

n

, implying that

n

and parameters that depend on

n

(including

tw

and

vc

) are insufficient for fixed-parameter tractability. For combined parameters, we give an

O^*(k^n)

-time algorithm, yielding single-exponential solvability for fixed

k

. While

k+tw

remains W[1]-hard, MAXSTP is in XP via an

O^*((n\cdot k)^{tw})

algorithm. Our results suggest that MAXSTP is often computationally harder than optimizing qualitative CSPs. We verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by

n

tw

. However, we also demonstrate that FPT algorithms for MAXSTP are indeed possible but with other parameters such as

k + vc

Johannes K. Fichte, Johanna Groven, Peter Jonsson +2

Department of Computer and Information Science (IDA) Linköping University

Satisfiability

Ask PDF