日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

経路計画arXiv:2610.09084

単一移動ラベル付きトークン経路問題の計算複雑性

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

シェア:XThreadsFacebookLINEはてブBluesky

中性原子量子コンピュータにおける原子移動に動機づけられた「単一移動ラベル付きトークン経路問題」を導入し、グリッドや平面グラフ上でのNP完全性、木におけるW[1]困難性などの計算複雑性を証明した。

詳しい要約

1. どんなもの?

- 中性原子量子計算機における原子移動を動機とした問題「Single-Move Labeled Token Routing」を導入。 - グラフの各source/target頂点にラベル集合が割り当てられ、tokenがsourceを占める。 - 解は、各sourceを互換target(ラベル集合が交差)に割り当てるmatching、各ペアのroute、token移動時にroute上に他tokenが無いmovement orderから成る。 - 既知の計算複雑性結果を拡張し、NP完全性やW[1]-hard性、FPT性を示す。

2. 先行研究と比べてどこがすごい?

- 全sourceが全targetと互換なら多項式時間可解、各sourceが丁度1つのtargetと互換ならgrid上でNP完全という既知結果を前提。 - 後者のNP完全性が、解がpairwise edge-disjoint routesを持つ場合でもgridおよび最大次数4のplanar graphで成立することを証明。 - 木では最大次数3でもNP完全という既知結果に対し、solution edge multiplicityをパラメータとしたW[1]-hard性、candidate edge multiplicity≤8でのNP完全性、およびFPT性を新たに示す。

3. 技術・手法の肝は?

- solution edge multiplicity(解のrouteが辺を共有する最大数)とcandidate edge multiplicity(互換ペアのpathが辺を共有する最大数)を定義。 - 木の最大次数3で、movement orderが与えられていてもsolution edge multiplicityのboundをパラメータとしてW[1]-hardであることを証明。 - 木の最大次数が非有界の場合、candidate edge multiplicity≤8でもNP完全であることを証明。 - 最大次数とcandidate edge multiplicityの組、およびcandidate vertex multiplicityによるFPTアルゴリズムを示す。

4. どうやって有効だと検証した?

- 理論的な計算複雑性の証明により検証。 - NP完全性、W[1]-hard性、FPT性の帰着・アルゴリズムを構成。 - 具体的な実験やデータセットによる検証は要旨からは不明。

5. 議論はある?

- 木において、最大次数またはcandidate edge multiplicityのいずれも省略できないことをP≠NPの仮定の下で示す。 - つまり、FPT性のパラメータとして両方が必要であることを議論。 - 他のグラフクラスやパラメータに関する議論は要旨からは不明。

6. 次に読むべき論文は?

- 要旨で参照されている先行研究:全sourceが全targetと互換な場合の多項式時間解法、grid上でのNP完全性、木の最大次数3でのNP完全性。 - 関連手法:Single-Move Labeled Token Routing、中性原子量子計算機におけるatom移動。 - 同分野の定番:token routing、multi-agent path finding、graph routing問題。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

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

分類: cs.CC, cs.DM, cs.DS, cs.RO, math.CO

原文アブストラクト

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. 1パナソニックHDなど、触覚に即応する両手作業AI「T-Rex」を共同開発研究・技術
  2. 2川崎重工業のロボット外販を報道新製品・発表
  3. 3Boston Dynamics、GlobalFoundriesでAtlasを試験へ 半導体製造で2027年初頭から半導体・GPU
  4. 4丸文、RealManのロボットアームやヒューマノイドを国内販売提携・買収
  5. 5NVIDIA、SC26で科学研究向けAIエージェントとHPC基盤を発表新製品・発表

PR・アフィリエイト広告

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI