PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.09084v1cs.CCcs.DMcs.DScs.ROmath.CO

TL;DR

Neutral-atom reconfiguration requires moving atoms to target positions along clear paths, and species-specific targets constrain which atoms can occupy them. The paper studies single-move routing with label-based compatibility across graph classes and parameterizations. It proves hardness even with disjoint routes in specified settings and establishes fixed-parameter tractability on trees under combined or vertex-based multiplicity bounds.

  • Problem

    Atom reconfiguration requires assigning atoms to target traps and choosing clear routes and a movement order, with mixed-species targets restricting acceptable assignments.

    Source: §1 · p. 2

  • Method

    The paper introduces Single-Move Labeled Token Routing, modeling compatibility through intersecting source and target label sets and studying graph classes and parameterizations.

    Source: §1 · p. 3, §7 · p. 48

  • Results

    The problem is NP-complete on grids and planar graphs of maximum degree four even when solvable instances admit pairwise edge-disjoint routes, and is fixed-parameter tractable on trees parameterized by maximum degree plus candidate edge multiplicity or candidate vertex multiplicity.

    Source: §7 · pp. 48, 50

  • Takeaways & Limitations

    The paper's algorithms also carry over when there are more sources than targets, with some sources left unmatched.

    Source: §7 · pp. 49–50

    The paper leaves open which compatibility restrictions yield tractability on trees when seeking solutions with small solution edge multiplicity.

    Source: §7 · p. 49

Abstract

from arXiv · show

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.

1 Introduction

Atom reconfiguration must assign atoms to targets, select empty-path routes, and order moves so atoms do not block one another. Single-Move Labeled Token Routing adds species-based compatibility, and the paper studies how compatibility and graph structure affect its complexity.

1 Introduction

  • Atom reconfiguration motivates the model: atoms are moved from occupied traps to empty targets along paths that are clear when used.Additional moves take time and create further opportunities for errors or atom loss.Source: §1 · p. 2
  • Species-specific targets make assignment consequential: exchanging atoms can produce an invalid target configuration.In mixed-species settings, a target may be designated for one species.Source: §1 · p. 2
  • Single-Move Labeled Token Routing assigns label sets to sources and targets, allowing a match exactly when their label sets intersect.A solution also chooses a route for each matched pair and a movement order that keeps each route free of other tokens.Source: §1 · p. 2
  • The paper asks how labels and graph structure affect complexity, focusing on how much information an algorithm must carry across a graph cut.Bounding solution-route overlap alone does not ensure tractability, while on trees the stated tractability results combine candidate-pair counts with degree or use vertex counts.Source: §1 · pp. 2–3

2 Related work

Prior atom-reconfiguration algorithms assume interchangeable atoms and may allow repeated moves, while other token-movement models vary in their move rules and target assignments. The paper studies arbitrary compatibility for path moves with each token moving at most once.

2 Related work

  • Earlier atom-reconfiguration algorithms assume interchangeable atoms, whereas this paper studies atoms compatible with arbitrary sets of targets.The earlier algorithms treat assignment, routes, and move order as parts of the problem; the paper notes that filling targets, when possible, can be done with each atom moving at most once [1].Source: §2 · p. 3
  • Other token-movement models use single-edge moves, simultaneous moves, or swaps, and differ in how tokens are assigned to targets.The paper's path move requires every vertex after the starting vertex to be unoccupied.Source: §2 · p. 3
  • Label sets express the model in which each token may be assigned to a set of targets, encompassing fixed-target and color-based assignment forms.The authors state that arbitrary compatibility relations for moves along paths of unoccupied vertices had not previously been studied.Source: §2 · p. 4
  • For monotone moves, fixed matching and routes permit a polynomial-time feasibility test, but choosing routes after fixing the matching can be hard.Monotone means that each token moves at most once [39]. The unique-matching case is NP-complete on 3 × w grids [2].Source: §2 · p. 4

3 Our contributions

The paper establishes tractability and hardness results for Single-Move Labeled Token Routing across graph classes and compatibility regimes. Its tree results show that some multiplicity bounds alone are insufficient, while combining candidate edge multiplicity with maximum degree, or bounding candidate vertex multiplicity, yields fixed-parameter tractability.

3 Our contributions

  • In the all-matching case, every connected instance is solvable, and a solution can be constructed in time O(n^2 + m).The all-matching criterion is equal numbers of sources and targets in every connected component.Source: §3 · p. 4
  • Unique-matching instances are NP-complete on grids and planar graphs of maximum degree four, even when solvable instances admit pairwise edge-disjoint routes.The planar result also holds at maximum degree three when solution edge multiplicity is at most two.Source: §3 · p. 5
  • On trees of maximum degree three, bounding solution edge multiplicity is W[1]-hard parameterized by that bound, even when a movement order is given.The problem is also NP-complete on these trees.Source: §3 · p. 5
  • On trees, the problem is NP-complete with candidate edge multiplicity at most eight, even when each source and target has at most three compatible partners.Candidate edge multiplicity counts compatible source-target pairs whose tree paths use an edge.Source: §3 · p. 5
  • On paths, the problem can be solved in time O(|I|).The vertex order forces the matching: the ith source must be matched to the ith target, after which compatibility is checked.Source: §3 · pp. 5–6
  • The problem is fixed-parameter tractable parameterized by the number of tokens.The approach guesses a matching and movement order, then checks whether suitable routes exist.Source: §3 · p. 6
  • On trees, the problem is fixed-parameter tractable parameterized by maximum degree plus candidate edge multiplicity, and also by candidate vertex multiplicity alone.The edge-based algorithm runs in time 2^O(∆·cm(I)^2) · |I|^O(1); the vertex-based algorithm runs in time 2^O(cvm(I)^2) · |I|^O(1). Neither maximum degree nor candidate edge multiplicity alone suffices unless P = NP.Source: §3 · p. 6

4 Preliminaries

The preliminaries formalize the graph, compatibility, route, and movement-order concepts used throughout the paper. They also establish an acyclicity test for movement feasibility, define multiplicity measures, and review the all-matching case.

4.1 Graph terminology

  • Grid graphs are subgraphs of rectangular integer grids, and every planar graph of maximum degree four has a polynomial-size orthogonal grid drawing computable in polynomial time.Source: §4.1 · p. 7

4.2 Instances, moves, and solutions

  • A solution combines a compatible source-target matching, one route per matched pair, and an order in which each route is clear when its token moves.Compatibility means the source and target label sets intersect; a route may be a trivial path when source and target coincide.Source: §4.2 · pp. 7–8
  • The problem belongs to NP because a matching, route family, and movement order form a polynomial-size certificate whose moves can be checked in polynomial time.Source: §4.2 · p. 8

4.3 Special cases and precedence digraphs

  • A route family admits a feasible movement order exactly when its precedence digraph is acyclic.Arcs encode moves that must precede another because a route uses that move’s source or target; a topological ordering then supplies a feasible order.Source: §4.3 · p. 8

4.4 Parameterized complexity and multiplicity

  • Solution edge multiplicity counts chosen routes sharing an edge, while candidate edge and vertex multiplicities count compatible-pair paths; on a star, these can be k and one, respectively.Source: §4.4 · p. 9

4.5 The all-matching case

  • Every connected all-matching instance is solvable in O(n2 + m) by repeatedly deleting spanning-tree leaves and ordering moves into target leaves early and out of source leaves late.The procedure matches a target leaf to a closest remaining source or a source leaf to a closest remaining target.Source: §4.5 · pp. 9–10

5 Hardness under structural and compatibility constraints

This section establishes hardness under structural and compatibility restrictions using reductions on planar graphs, grids, and trees. It considers guarantees including unique matching, edge-disjoint routes in solvable instances, bounded solution or candidate edge multiplicity, and a supplied movement order.

5 Hardness under structural and compatibility constraints

  • Hardness persists on grids and planar graphs of maximum degree four with a unique compatible matching and pairwise edge-disjoint routes; tree hardness also holds under the stated multiplicity bounds.On maximum-degree-three trees, matching choice is W[1]-hard parameterized by solution edge multiplicity even when a movement order is given; on unbounded-degree trees, the problem is NP-complete with candidate edge multiplicity at most eight.Source: §5 · pp. 10–11

5.2 Unique matching with edge-disjoint routes on planar graphs and grids

  • The subsection’s constructions establish hardness on grids and planar graphs even with a unique matching and, for yes-instances, a solution with edge-disjoint routes.This contrasts with the cited 3 × w grid instances, where every solution has an edge used by at least one third of the routes.Source: §5 · pp. 10–11, §5.2 · p. 12

5.1 Reducing the degree of ordinary vertices

  • Expanding an ordinary vertex of degree at least four into a maximum-degree-three tree preserves whether the instance is solvable, while preserving tree structure and, when applicable, planarity.The replacement tree has one leaf per neighbor; its new vertices are ordinary and remain unoccupied.Source: §5.1 · p. 11

5.2.1 The reduction on general graphs

  • The general-graph reduction proves unique-matching instances NP-complete even when every solution has pairwise edge-disjoint routes.Variable assignment tokens choose true or false paths; blocking and delay tokens constrain which literal path a clause token can use, encoding satisfiability.Source: §5.2.1 · pp. 14, 16

5.2.2 A planar realization

  • The planar realization modifies the clause gadgets and fixes the order of vertices on variable paths to produce a planar instance in polynomial time.The passage introduces this modification and points to a later proof for the resulting construction.Source: §5.2.2 · p. 17
  • The planar construction orders variable paths by occurrence ports and modifies three-literal clause gadgets with crossing vertices, preserving the unique matching and the route properties used to encode satisfying assignments.In every solution, assignment tokens use a true or false path, while each clause-token route contains the blocking target and delay source of some occurrence; the reduction uses these properties to recover a satisfying assignment.Source: §5.2.2 · pp. 18, 20, 21, 23
  • Unique-matching routing is NP-complete on planar graphs of maximum degree four even with edge-disjoint yes-solutions, and on planar graphs of maximum degree three even with yes-solutions of edge multiplicity at most two.The degree-three result follows by replacing degree-four ordinary vertices with trees; at most two routes then share an edge in the constructed solution.Source: §5.2.2 · p. 23

5.2.3 Grids and grid graphs

  • Subdividing edges with ordinary vertices preserves feasibility in both directions, enabling the planar reduction to transfer to grid graphs without changing whether the instance is solvable.The reverse direction contracts each subdivided path; internal vertices of the contracted routes remain unoccupied when tokens move.Source: §5.2.3 · p. 24
  • Unique-matching routing is NP-complete on grids and grid graphs, even when every solvable constructed instance admits a solution with pairwise edge-disjoint routes.The reduction draws the planar maximum-degree-four graph on an orthogonal grid and uses its grid points to form a subdivision.Source: §5.2.3 · p. 24
  • Unique-matching instances are NP-complete on grids, even when every solvable instance admits a solution with pairwise edge-disjoint routes.The hardness is established first on grid graphs and then extended to grids by padding with fixed self-matched tokens.Source: §5.2.3 · pp. 24–25

5.3 Solution edge multiplicity on trees of maximum degree three

  • On trees of maximum degree three, Single-Move Labeled Token Routing is W[1]-hard parameterized by solution edge multiplicity, even when a movement order is given.The bound on solution edge multiplicity is supplied as part of the input.Source: §5.3 · p. 25
  • In any solution, each cell's tile target forces a legal tile whose column and row tile tokens move to the tile target and corresponding local target, unsealing both value subtrees.At most one value subtree per row or column can be unsealed, so these forced choices encode consistent row and column values.Source: §5.3 · p. 31
  • For Single-Move Labeled Token Routing on trees of maximum degree three, the problem is NP-complete and W[1]-hard parameterized by input bound µ, even when a movement order is given.Source: §5.3 · p. 31

5.4 Candidate edge multiplicity on trees of unbounded degree

  • In the candidate-multiplicity reduction, each compatible matching encodes a variable assignment and selects one occurrence per clause; a false selected occurrence creates a precedence cycle, preventing a feasible movement order.The cycle is ax, ℓo, co, wo, ax when occurrence o is selected and false.Source: §5.4 · pp. 34, 36, 37
  • Candidate edge multiplicity at most eight still permits NP-completeness on trees of unbounded degree, even when each source and target has at most three compatible partners.The constructed tree has maximum degree eleven away from its common vertex; its candidate edge multiplicity is at most eight.Source: §5.4 · pp. 35, 37
  • The reduction’s satisfying-assignment schedule moves every token once along its matched pair’s unique path, using seven stages to keep each route clear.The stages move unselected choice and false witness tokens, assignment tokens, literal tokens, selected-clause and filler tokens, remaining witnesses, then complement tokens.Source: §5.4 · p. 38
  • Single-Move Labeled Token Routing is NP-complete on trees of unbounded degree even when candidate edge multiplicity is at most eight.The reduction is from 4-Bounded 3-SAT; the construction supplies a satisfying-assignment movement order, and the proof establishes membership in NP.Source: §5.4 · p. 38
  • Replacing the construction’s high-degree vertex with a maximum-degree-three tree can make its edges carry an unbounded number of literal and witness paths.The paths through the replacement tree depend on which gadgets it separates, so the multiplicity is not bounded by a constant for arbitrary formulas.Source: §5.4 · p. 38
  • Unless P = NP, any hardness result with bounded candidate edge multiplicity must allow unbounded maximum degree, since bounded degree together with bounded candidate edge multiplicity is tractable.The passage notes that the degree-three replacement does not preserve a constant bound on candidate edge multiplicity.Source: §5.4 · p. 38

6 Positive results beyond the all-matching case

This section develops tractability results for paths, bounded token counts, and trees. For trees, it gives fixed-parameter algorithms using bounded candidate edge multiplicity together with maximum degree, or bounded candidate vertex multiplicity, and describes a dynamic program based on subtree boundary pairs and precedence constraints.

6.1 Paths

  • On paths, Single-Move Labeled Token Routing can be solved in O(|I|) time because any solution must use the matching that pairs the ith source with the ith target.The algorithm checks compatibility for each such pair and constructs a feasible movement order when all pairs are compatible.Source: §6.1 · p. 39

6.2 A bounded number of tokens

  • Parameterized by the number k of tokens, Single-Move Labeled Token Routing is fixed-parameter tractable by enumerating compatible matchings and movement orders and testing route reachability.The algorithm tries k! bijections and k! source orderings, using breadth-first search to test each move in the graph with other occupied vertices removed.Source: §6.2 · p. 40

6.3 Bounded candidate edge multiplicity on bounded-degree trees

  • On trees, bounded candidate edge multiplicity together with bounded maximum degree yields a fixed-parameter algorithm based on bottom-up dynamic programming.Each subtree state records its compatible pairs crossing the boundary edge and the precedence relation forced among them; the algorithm accepts when the root’s empty state is true.Source: §6.3 · pp. 40, 41, 43, 45
  • Single-Move Labeled Token Routing on trees is solvable in time 2^O(∆·cm(I)^2)·|I|^O(1), so it is fixed-parameter tractable parameterized by ∆+cm(I).Neither maximum degree nor candidate edge multiplicity can be dropped from this parameterization unless P = NP.Source: §6.3 · p. 46

6.4 Bounded candidate vertex multiplicity

  • Candidate vertex multiplicity cvm(I) alone yields a tree algorithm running in time 2^O(cvm(I)^2)·|I|^O(1), and hence fixed-parameter tractability.The algorithm bounds the dynamic-programming exponent using the number of compatible-pair paths through each vertex, without requiring bounded maximum degree.Source: §6.4 · p. 47
  • The parameterizations are incomparable in running time: Theorem 8 is faster under its bound, while Theorem 9 applies to unbounded-degree trees with bounded candidate vertex multiplicity.The observation cm(I) ≤ cvm(I) ≤ ∆·cm(I)+1 explains both the parameter relationship and why substituting into Theorem 9 gives a weaker bound than Theorem 8.Source: §6.4 · pp. 47–48
  • Unless P = NP, no NP-hardness reduction to tree instances can produce only instances of constant candidate vertex multiplicity.The cited construction has candidate edge multiplicity at most eight, but candidate vertex multiplicity at least twice its number of occurrences.Source: §6.4 · p. 48

7 Conclusion and open problems

The conclusion gathers the paper’s hardness and tractability results, then identifies open boundaries involving routes, graph structure, compatibility, and relaxed assumptions. It also distinguishes established extensions from questions that remain unresolved.

7 Conclusion and open problems

  • Unique-matching instances remain NP-complete on grids and planar graphs even when solvable instances admit pairwise edge-disjoint routes.The paper also establishes planar hardness at maximum degree three when solution edge multiplicity is at most two.Source: §7 · p. 48
  • On degree-three trees, bounded solution edge multiplicity is W[1]-hard even with a supplied order; unbounded-degree trees are NP-complete at candidate edge multiplicity at most eight.The latter two results are proved in this paper.Source: §7 · p. 48
  • Tree algorithms are fixed-parameter tractable by maximum degree plus candidate edge multiplicity, or by candidate vertex multiplicity alone; neither maximum degree nor candidate edge multiplicity can be omitted unless P=NP.The paper also gives a linear-time algorithm on paths and a fixed-parameter algorithm by number of tokens.Source: §7 · p. 48
  • Prior 3 × w grid hardness forces shared crossing edges when there are more than three tokens, whereas this paper’s edge-disjoint-route construction leaves source-target overlap as an open boundary.The construction of Theorem 3 places a token whose source is its target at every vertex missing from the grid graph.Source: §7 · pp. 48–49
  • The grid hardness construction uses source-equals-target tokens at missing vertices; whether hardness persists without them or with routes containing only constantly many other sources and targets remains open.The construction also permits a route to pass through unboundedly many other tokens’ sources and targets.Source: §7 · p. 49
  • Beyond trees, pathwidth bounds alone do not yield tractability; the paper leaves open whether combining graph structure with compatibility measures can help.It also asks whether a structural parameter other than graph width can yield fixed-parameter tractability by itself.Source: §7 · p. 49
  • For colorings, two-color hardness is known on degree-three trees, but whether Theorem 4 or bounded-label versions of Theorems 4 and 5 hold remains open.Theorem 5 can be made a coloring instance through the construction changes described in the conclusion.Source: §7 · p. 49
  • Allowing more than one move leaves open whether Theorem 7 extends, although unique-matching grid instances remain NP-hard when each token moves at most twice.When there are more sources than targets, the paper’s hardness results and algorithms carry over; on paths, omitted sources can be selected in polynomial time, but preserving linear time is unknown.Source: §7 · pp. 49–50
Loading 2610.09084v1…