本研究は、グラフ上のエージェント移動問題、特に木構造（Trees）における最適化問題の複雑性を対象としている。対象となる問題は、個々のエージェントが識別される「labeled」ケースと、エージェントが色によってグループ化される「$k$-colored」ケースである。最適化の指標としては、全エージェントの到着完了時刻の最大値であるmakespan $\max_i T_i$、到着時刻の総和であるflowtime $\sum_i T_i$、および全移動距離の総和であるtotal distanceを検討している。特に、木におけるtotal distanceの最適化は、隣接する空き頂点へペブルを移動させるPebble Motion on Trees (PMT) と等価である。
本論文の主な貢献は、Stack Rearrangement (SR) 問題を基盤とした、木構造における様々な移動問題の困難性を一括して証明するフレームワークの提示である。具体的には、labeled PMTおよび2-colored PMTが、距離、makespan、flowtimeのすべての標準的な目的関数においてNP困難であることを示した。これにより、unlabeled（1-colored）ケースがネットワークフローにより多項式時間で解けるのに対し、2-coloredが困難となる境界を特定した。また、PMTのNP困難性を、深さ3のsubdivided starsや最大次数3の木といった極めて制約の強いグラフクラスにおいて証明した点は、既存の2Dグリッド上での結果を大幅に強化するものである。
困難性の証明には、Stack Rearrangement (SR) 問題からの帰着が用いられている。まず、Labeled Stack Rearrangement (LSR) がMinimum Feedback Arc Set (MFAS) 問題からNP困難であることを示し、これを用いてPMTへの帰着を行う。LSRの各スタックをパスとして扱い、スタックの深さに応じた長さのパスを構成することで、LSRの再配置回数 $k$ とPMTの移動コスト $D + 2k$（$D$ は最短経路距離の総和）の間の関係を導出している。また、2-colored SRの困難性は3-Partition問題からの帰着により証明されており、各アイテムが最大1回しか移動できない制約下での構成が用いられている。MAPFのflowtimeの証明では、再配置の順序が指標に与える影響を制御するために、ゲートエージェントとパディングエージェントを用いた特殊な構成を導入している。
提案された手法により、以下の条件下でのNP困難性が検証されている。第一に、PMTにおいて、(i) 深さ3のsubdivided stars、または (ii) 最大次数3の木という非常に単純な構造においても、labeledおよび2-coloredのケースでNP困難性が成立することが示された。第二に、MAPFのmakespanについては、LSRの解が $m$ 手であればmakespanが $2m+1$ 以下となる帰着により、NP困難性が導かれている。第三に、flowtimeについても、2-colored SRからの帰着、およびlabeledケースにおけるパディングエージェントを用いた構成により、NP困難性が証明されている。さらに、Lemma $\tilde{4.3}$ により、PMTの解が最短経路の下界を達成する場合、移動を連続的な最短経路移動として再構成できることが示され、依存グラフ上のサイクル検出を用いることで、木上のlabeled PMTにおける下界達成可能性が多項式時間で判定可能であることが確認された。
本研究の結果は、木構造における移動問題の計算複雑性の境界をタイトに特定している。ラベルなし（1-colored）の場合は多項式時間で解けるが、2色以上のカラーバリアントではNP困難になるという境界が明確になった。また、最大次数が3で困難となり、次数2（パス構造）では効率的に解けるという点も、問題の構造的性質を浮き彫りにしている。2Dグリッド上では下界達成可能性問題自体がNP困難であるのに対し、木構造では多項式時間で判定可能であるという発見は、木特有の性質を示唆している。今後の課題として、木の深さ、最大次数、分岐頂点数などのパラメータをさらに削減し、NP困難性と多項式時間解法の正確な境界を特定することが挙げられている。
本論文は、木構造におけるマルチエージェント経路探索（MAPF）の複雑性を、距離、メイクスパン、フロータイムの標準的な目的関数および、エージェントが区別される「labeled」と、色が同じなら入れ替え可能な「colored」のバリエーションにわたって解明するフレームワークを提示している。著者らは、木構造におけるlabeled MAPFおよび2-colored MAPFが、これらすべての目的関数においてNP困難であることを証明した。特に、一度に一つのペブルを隣接する空き頂点へ移動させ、総移動回数を最小化する古典的なPebble Motion問題の木構造における複雑性を、数十年の未解決問題を経て解決した。これらの困難性は、スタック内のアイテムを最適に並べ替える「Stack Rearrangement」問題のNP困難性を証明することで導出されており、この手法を用いることで、非常に単純な木構造である「subdivided stars」においても困難性が成立することを示している。また、colored Pebble Motionについても、2色という最小の条件下で、任意のグラフクラスにおける初の困難性結果（tightな結果）を与えている。
本研究は、グラフ上のPebble Motion (PMG) およびその並列版であるMulti-Agent Path Finding (MAPF) において、木構造（Trees）上での最適解を求める問題の計算複雑性を解明している。具体的には、エージェントが個別に識別される「labeled」ケースと、チームごとに識別される「$k$-colored」ケースを対象とし、最適化指標としてmakespan（全エージェントの到着完了時間）、flowtime（到着時間の総和）、およびtotal distance（全エージェントの移動距離の総和）を検討している。著者らは、Stack Rearrangement (SR) 問題からの帰着を用いるフレームワークを提案し、全ての検討対象となる指標およびラベル付き・色付きの全てのバリエーションが、極めて単純な木構造である「subdivided stars（中心頂点から複数のパスが伸びる構造）」においてNP困難であることを証明した。特に、2-coloredのケースは、unlabeled（1-colored）の場合がネットワークフローへの帰着により多項式時間で解けることに対し、NP困難となる境界（tractability threshold）を特定している。また、labeled PMTのNP困難性は、最大次数3の櫛状の木（comb-like trees）においても成立することを示し、既存の2Dグリッド上での結果を強化している。
本セクションでは、グラフ上でのエージェント移動に関する諸問題の定義がなされている。Pebble Motion on Graphs (PMG) は、連結無向グラフ $G=(V, E)$ 上の $k$ 個のラベル付きエージェント（pebbles）を、隣接する空き頂点へ移動させることで、初期配置 $\mathcal{C}_{start}$ から目標配置 $\mathcal{C}_{target}$ へと最小手数で遷移させる問題である。グラフ $G$ が木である場合は Pebble Motion on Trees (PMT) と呼ばれ、Multi-Agent Path Finding (MAPF) は、エージェントが待機または移動を選択できる離散時間モデルにおいて、頂点衝突やエッジ衝突を回避しつつ目標に到達する経路集合を求める問題として定義される。MAPFの最適化指標には、最大完了時刻である makespan $\max_i T_i$、完了時刻の総和である flowtime $\sum_i T_i$、および全エージェントの総移動距離が用いられ、木における total distance 最適化は PMT と等価である。また、スタックの容量 $d_j$ を持つ複数のスタック間でオブジェクトを pop-and-push する Labeled Stack Rearrangement (LSR) も定義されており、これら全ての問題において、オブジェクトを色クラスに分割し、目標位置に指定された色のオブジェクトが到達すればよいとする colored variant が導入されている。
本セクションでは、他の問題への帰着の基礎となるStack Rearrangement (SR) の困難性が示されている。まず、Labeled Stack Rearrangement (LSR) は、スタックの深さが3に制限された場合でもNP困難であることが、Minimum Feedback Arc Set (MFAS) 問題からの帰着により証明されている。この帰着では、グラフの頂点 $v \in V$ に対してオブジェクト $v$ を、辺 $(u, v) \in E$ に対してオブジェクト $u_{start}$ と $v_{target}$ を割り当て、頂点のトポロジカル順序がオブジェクトの移動順序に対応するように構成することで、MFASの解のサイズとLSRの追加移動回数の関係を $n + |E| - |F|$（$F$ はフィードバック弧集合）として導いている。次に、2-colored SR（アイテムに2色の属性がある場合）についても、各アイテムが最大1回しか移動しないという制約下での決定問題がNP困難であることが、3-Partition問題からの帰着により示されている。この構成では、3-Partitionの各整数 $a_i$ に対して、赤色アイテムを含むアイテムスタック $S_i$ と、青色アイテムを含むチェックポイントスタック $C_i$ を作成し、アイテムが1回のみ移動できる条件下では、チェックポイントスタックをクリアする過程でアイテムスタックの赤色ターゲット容量を管理することが、3-Partitionの各トリプルが合計 $B$ になることと等価であることを利用している。
本セクションでは、Stack Rearrangement (LSR) 問題から Pebble Motion on Trees (PMT) 問題への帰着を通じて、PMT の計算困難性を証明している。定理 4.1 により、PMT は (i) 深さ 3 の細分されたスターグラフ、または (ii) 最大次数 3 の木に制限された場合でも NP 困難であることが示された。帰着において、LSR の各スタックをパスとして扱い、スタックの深さに応じた長さのパスとして構成することで、LSR の再配置（relocation）の有無と、PMT の移動コストが最短経路距離の総和 $D = \sum_{p \in \text{pebbles}} \text{dist}(\text{start}_p, \text{goal}_p)$ に対して $2k$ の追加コスト（$k$ は再配置数）を伴うかどうかの判定問題が結び付けられる。具体的には、LSR で $k$ 回の再配置で解けることは、PMT でコスト $D + 2k$ 以内で解けることと等価である。また、2色付きの PMT (2-colored PMT) についても、2色付き LSR からの帰着により、同様にスターグラフや最大次数 3 の木において NP 困難であることが示されている。この証明には、ペブルの移動を最短経路に沿った「原子的な（atomic）」移動の集合として再構成できることを示す補題 4.3 が重要な役割を果たしている。
本セクションでは、木構造（特に深さ3の細分されたスターグラフ）におけるMAPFのmakespanおよびflowtimeの最適化問題がNP困難であることを証明している。まず、makespanについては、スタック深さ3のLSR（Labeled Stack Reconfiguration）問題からの帰着により、LSRの解が$m$手であれば、対応するMAPFのmakespanが$2m+1$以下となることを示し、NP困難性を導いている。次に、2色（2-colored）MAPFのflowtimeについては、2-colored SR問題からの帰着を用い、SRの再配置（relocation）が$m$回であれば、flowtimeが$\sum_{v \in \mathcal{V}_{target}} (d(v, \text{target}(v)) + 1) + 2m$となることを利用してNP困難性を示している。ラベル付き（labeled）MAPFのflowtimeについては、再配置の順序がflowtimeに与える影響を制御するため、ゲートエージェントとパディングエージェントを用いた特殊な構成を導入している。この構成では、再配置が$m$回以下であればflowtimeが$F_{min} + 2m$以下となる一方、再配置が$m$回を超えると、パディングエージェントの遅延によりflowtimeが$F_{min} + 2(m+1)$以上となるように設計されており、これによりLSR問題のNP困難性がMAPFのflowtime問題へ帰着される。
本研究は、スタックベースの動作が様々な運動調整問題における困難性の共通の源泉であることを示し、木構造上でのペブル動作（Pebble Motion on Trees; PMT）の複雑性に関する長年の問題を解決した。提案されたフレームワークは、距離、メイクスパン、フロータイムといった異なる目的関数に対して同一の還元構造を適用可能であり、木のような制約の強い設定における困難性証明の再利用可能な基盤となる。結果は、ラベルなしの動作が効率的に解けるのに対し、2色以上のカラーバリアントでは困難になる点や、最大次数が 3 で困難になり次数 2（パス構造）では効率的に解ける点など、自然な境界においてタイトである。また、Lemma $\tilde{4.3}$ により、PMTの解が最短経路の下界を達成する場合、各ペブルの移動を連続的な最短経路移動として並べ替えることが可能であり、依存グラフ上のサイクル検出を用いることで、木上のラベル付きPMTにおいてこの下界の達成可能性を多項式時間で判定できることを示した。これは、2Dグリッド上では同様の下界達成可能性問題が NP困難であることと比較して特筆すべき性質であり、今後は木の深さ、最大次数、分岐頂点数などのパラメータを削減することで、NP困難性と多項式時間解法の正確な境界を特定することが課題である。