論文の概要: On the complexity of the single-move labeled token routing problem

• arxiv url: http://arxiv.org/abs/2610.09084v1
• Date: Tue, 06 Oct 2026 20:29:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.598348
• Title: On the complexity of the single-move labeled token routing problem
• Title（参考訳）: シングルモーブラベル付きトークンルーティング問題の複雑さについて
• Abstract要約: 中性原子量子コンピュータでは、原子は空の位置の経路に沿って標的位置に移動され、標的位置は1つの種類の原子に予約される。 グラフのすべてのソースとすべてのターゲットにラベルのセットが割り当てられ、トークンがソースを占有する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: 中性原子量子コンピュータでは、原子は空の位置の経路に沿って標的位置に移動され、標的位置は1つの種類の原子に予約される。 グラフのすべてのソースと全てのターゲット頂点がラベルのセットに割り当てられ、トークンがソースを占有する。 解は、各ソースを互換性のあるターゲット(ラベルセットが自身と交差する)に割り当てるマッチングと、マッチしたペアのルートと、トークンを移動したときに他のトークンを含まない移動順序からなる。 この問題は、すべてのソースがすべてのターゲットと互換性があるときに多項式時可解であることが知られ、各ソースがちょうど1つのターゲットと互換性があるとき、グリッドグラフ上で$\mathsf{NP}$-completeが成立することが知られている。 後者のケースは、ある解が対の辺非連結経路を持つ場合でも、格子および最大次数4の平面グラフ上で$\mathsf{NP}$完全であることを証明する。 木では、問題は最大次数3であっても$\mathsf{NP}$-完全であることが知られている。 我々は,解エッジ乗数,解の最大経路数,エッジを共有する解の最大経路数,エッジの最大経路数,エッジが共有する相似ペアの最大数の候補エッジ乗数を通して木について検討する。 最大次数3のツリー上では、問題は解エッジ乗法上の有界化によってパラメータ化される$\mathsf{W}[1]$-hardであり、運動順序が与えられたとしても、非有界化のツリーでは、候補エッジ乗法が最大8である場合でも$\mathsf{NP}$-completeであることを示す。 木木では、問題は最大度でパラメータ化され、エッジの候補乗算と、頂点の候補頂点乗算によってもパラメータ化される。 $\mathsf{P}=\mathsf{NP}$ がなければ、最大次数も候補エッジ乗法も省略できない。

関連論文リスト

• Approximating Optimal Labelings for Temporal Connectivity [7.394099294390271]
  時間グラフのエッジの可利用時間を、与えられた最大許容時間$a$で全ての頂点が接続されるようにスケジューリングする問題について検討する。 この問題は、EmphMinimum Aged Labeling (MAL)として知られるもので、ロジスティクス、流通スケジューリング、ソーシャルネットワークに広がる情報にいくつかの応用がある。
  論文  参考訳（メタデータ） (2025-04-23T16:00:33Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology [0.0]
  我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。 解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。 MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
  論文  参考訳（メタデータ） (2023-12-15T09:42:46Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem [2.107421958337625]
  有限グラフ $(X,E)$ に対する逆問題を考える。 この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
  論文  参考訳（メタデータ） (2023-06-08T14:48:48Z)
• Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
  古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。 NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
  論文  参考訳（メタデータ） (2023-05-26T05:31:25Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。 本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
  論文  参考訳（メタデータ） (2021-12-08T08:23:37Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。