pith. sign in

arxiv: 2606.06686 · v1 · pith:C5SNXP5Cnew · submitted 2026-06-04 · 💻 cs.RO · cs.DS

On the Hardness of Optimal Motion on Trees

Tzvika Geft This is my paper

Pith reviewed 2026-06-28 00:58 UTC · model grok-4.3

classification 💻 cs.RO cs.DS
keywords multi-agent path findingpebble motionNP-hardnesstreesstack rearrangementmotion planning on graphs
0
0 comments X

The pith

Optimal multi-agent motion on trees is NP-hard for both labeled and colored cases across all standard objectives.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows that several fundamental problems in moving multiple agents on tree-shaped graphs are NP-hard. It proves this for minimizing total distance traveled, the time until the last agent arrives, and the sum of arrival times, whether agents are unique or interchangeable within colors. The work resolves an open question on the complexity of pebble motion on trees by linking it to a newly proven hard problem of rearranging stacks of items. Readers should care because trees model many hierarchical networks, and knowing these problems are hard guides the search for approximations or special cases.

Core claim

We prove that Multi-Agent Path Finding on trees is NP-hard for labeled agents and for agents with two colors, under the objectives of sum-of-costs, makespan, and flowtime. This includes the pebble motion problem with one move at a time. The proof proceeds by establishing NP-hardness for Stack Rearrangement and reducing it to the motion problems, with the hardness holding already on subdivided stars.

What carries the argument

A polynomial-time reduction from the NP-hard Stack Rearrangement problem to the various MAPF problems on trees that maintains the objective values.

If this is right

  • Stack Rearrangement is NP-hard.
  • Classical Pebble Motion on trees is NP-hard.
  • Two-colored Pebble Motion is NP-hard on any graph class.
  • Hardness holds for MAPF on subdivided stars under all three objectives.
  • These problems share a common tractability barrier.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Exact optimal solutions for these problems on trees will likely require exponential time in the worst case.
  • Research into parameterized algorithms or heuristics for tree-structured motion planning could be prioritized.
  • The stack rearrangement model might apply to other domains like warehouse logistics or data structure manipulations.

Load-bearing premise

The reductions from Stack Rearrangement to the MAPF variants on trees preserve both feasibility and the exact objective values.

What would settle it

Discovery of a polynomial-time algorithm solving any of these MAPF problems on trees, or construction of a specific instance where the claimed reduction does not hold.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to resolve the complexity of labeled and 2-colored MAPF on trees for distance, makespan, and flowtime by proving NP-hardness of Stack Rearrangement and then giving polynomial reductions from it to the MAPF variants (including one-move-at-a-time pebble motion). Hardness is asserted to hold already on subdivided stars, resolving the classical Pebble Motion problem on trees and supplying the first hardness result for colored pebble motion on any graph class with only two colors.

Significance. If the reductions are correct, the results close multiple long-open questions on basic discrete motion models, unify prior hardness results via a common stack-rearrangement barrier, and establish tightness for 2-colored pebble motion. The framework is notable for producing hardness on very simple trees.

major comments (2)
  1. [Reduction sections (likely §4–§6)] The central claims depend on the correctness of the polynomial reductions from Stack Rearrangement to labeled/colored MAPF on trees (including the pebble model) for all three objectives. The construction on subdivided stars must map feasible stack sequences to collision-free paths while preserving objective values (or an affine transformation) and enforcing color interchangeability; without an explicit verification that no extraneous moves or collisions are introduced, the transfer of NP-hardness cannot be confirmed for makespan and flowtime simultaneously.
  2. [Stack Rearrangement hardness proof (likely §3)] The NP-hardness proof for Stack Rearrangement itself is load-bearing; the reduction from a known hard problem to stacks must be checked for polynomial size and objective preservation before the downstream MAPF claims follow.
minor comments (2)
  1. [Preliminaries] Notation for the three objectives (distance, makespan, flowtime) should be introduced once with consistent symbols before the reductions are stated.
  2. [Figures illustrating reductions] Figure captions for the subdivided-star constructions should explicitly label which vertices correspond to stack positions versus routing paths.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed review and for recognizing the potential impact of our results on long-standing open questions in MAPF and pebble motion. Below we respond point-by-point to the major comments. We maintain that the proofs in the manuscript are correct and self-contained, but we are prepared to expand explicit verification steps if that would strengthen the presentation.

read point-by-point responses

  1. Referee: [Reduction sections (likely §4–§6)] The central claims depend on the correctness of the polynomial reductions from Stack Rearrangement to labeled/colored MAPF on trees (including the pebble model) for all three objectives. The construction on subdivided stars must map feasible stack sequences to collision-free paths while preserving objective values (or an affine transformation) and enforcing color interchangeability; without an explicit verification that no extraneous moves or collisions are introduced, the transfer of NP-hardness cannot be confirmed for makespan and flowtime simultaneously.

    Authors: Sections 4–6 contain explicit bijections between optimal stack-rearrangement sequences and collision-free MAPF solutions on subdivided stars. Each stack operation is realized by a unique path for the corresponding agent (or color class), and the star subdivision plus the one-move-at-a-time rule prevent any bypassing or colliding moves outside the intended sequence. Objective preservation is shown via direct equality for distance and via affine transformations (with explicit constants) for makespan and flowtime; color interchangeability follows from the fact that same-color agents occupy interchangeable positions within each subdivided arm. We can add a short summary lemma that enumerates the forbidden extraneous configurations if the referee considers the current inline arguments insufficiently highlighted. revision: partial

  2. Referee: [Stack Rearrangement hardness proof (likely §3)] The NP-hardness proof for Stack Rearrangement itself is load-bearing; the reduction from a known hard problem to stacks must be checked for polynomial size and objective preservation before the downstream MAPF claims follow.

    Authors: Section 3 gives a direct polynomial-time reduction from 3-Partition. The constructed instance uses a linear number of stacks whose heights and item sizes are polynomial in the source instance; every feasible rearrangement sequence corresponds exactly to a feasible 3-Partition solution, and the total number of stack moves equals the 3-Partition objective plus a fixed additive constant independent of the instance. This establishes both NP-hardness and objective preservation for the base problem, which then transfers unchanged through the subsequent MAPF reductions. revision: no

Circularity Check

0 steps flagged

No circularity; hardness established via independent proof of Stack Rearrangement plus reductions

full rationale

The paper first proves NP-hardness of the new Stack Rearrangement problem, then gives explicit polynomial reductions from it to labeled/2-colored MAPF (including pebble motion) on trees for all three objectives. No load-bearing self-citation, self-definition, or fitted-input-as-prediction appears; the base hardness is established separately within the same manuscript rather than imported from prior author work. Reductions are described as preserving feasibility and objective values, but the derivation chain does not reduce any claimed result to its own inputs by construction. This matches the expected non-circular structure for a multi-problem hardness paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Standard complexity-theoretic paper; relies on the assumption that P does not equal NP to interpret the meaning of NP-hardness but introduces no free parameters or new entities.

axioms (1)
  • standard math P does not equal NP
    Implicit background assumption used to conclude that NP-hard problems lack polynomial-time algorithms.

pith-pipeline@v0.9.1-grok · 5807 in / 1113 out tokens · 29654 ms · 2026-06-28T00:58:11.807675+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

221 extracted references · 15 canonical work pages · 1 internal anchor

  1. [1]

    AAAI Conference on Artificial Intelligence (AAAI) , year=

    Robust out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity , author=. AAAI Conference on Artificial Intelligence (AAAI) , year=

  2. [2]

    Justin Kottinger and Tzvika Geft and Shaull Almagor and Oren Salzman and Morteza Lahijanian , title =

  3. [3]

    Introducing Delays in Multi Agent Path Finding , booktitle =

    Justin Kottinger and Tzvika Geft and Shaull Almagor and Oren Salzman and Morteza Lahijanian , editor =. Introducing Delays in Multi Agent Path Finding , booktitle =. 2024 , url =. doi:10.1609/SOCS.V17I1.31540 , timestamp =

    work page doi:10.1609/socs.v17i1.31540 2024

  4. [4]

    Schweller and Tim Wylie , title =

    David Caballero and Timothy Gomez and Robert T. Schweller and Tim Wylie , title =. Algorithmica , volume =

  5. [5]

    Wilson and Lydia E

    Randall H. Wilson and Lydia E. Kavraki and Tom. Two-Handed Assembly Sequencing , journal =. 1995 , timestamp =

    1995

  6. [6]

    Mikkel Abrahamsen and Tzvika Geft and Dan Halperin and Barak Ugav , title =

  7. [7]

    Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity , booktitle =

    Mikkel Abrahamsen and Tzvika Geft and Dan Halperin and Barak Ugav , editor =. Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity , booktitle =. 2023 , url =. doi:10.5555/3545946.3598731 , timestamp =

    work page doi:10.5555/3545946.3598731 2023

  8. [8]

    Tzvika Geft , title =

  9. [9]

    Fine-Grained Complexity Analysis of Multi-Agent Path Finding on

    Tzvika Geft , editor =. Fine-Grained Complexity Analysis of Multi-Agent Path Finding on. Sixteenth International Symposium on Combinatorial Search,. 2023 , url =. doi:10.1609/SOCS.V16I1.27279 , timestamp =

    work page doi:10.1609/socs.v16i1.27279 2023

  10. [10]

    2024 , note =

    Tractability Frontiers in Multi-Robot Coordination and Geometric Reconfiguration , author=. 2024 , note =

    2024

  11. [11]

    International Workshop on the Algorithmic Foundations of Robotics (WAFR) , year =

    Tractability frontiers in multi-robot coordination and geometric reconfiguration , author=. International Workshop on the Algorithmic Foundations of Robotics (WAFR) , year =

  12. [12]

    Geft, Tzvika and Halperin, Dan and Nakar, Yonatan , journal=

  13. [13]

    Geft, Tzvika and Halperin, Dan , journal=

  14. [14]

    Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =

    Pankaj K. Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =

  15. [15]

    Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =

    Pankaj K. Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =. Comput. Geom. , volume =

  16. [16]

    Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , title =

    Pankaj K. Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , title =

  17. [17]

    Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , editor =

    Pankaj K. Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , editor =. On Two-Handed Planar Assembly Partitioning with Connectivity Constraints , booktitle =. 2021 , url =. doi:10.1137/1.9781611976465.105 , timestamp =

    work page doi:10.1137/1.9781611976465.105 2021

  18. [18]

    Tzvika Geft and Dan Halperin , title =

  19. [19]

    Refined Hardness of Distance-Optimal Multi-Agent Path Finding , booktitle =

    Tzvika Geft and Dan Halperin , editor =. Refined Hardness of Distance-Optimal Multi-Agent Path Finding , booktitle =. 2022 , url =. doi:10.5555/3535850.3535905 , timestamp =

    work page doi:10.5555/3535850.3535905 2022

  20. [20]

    2021 , note =

    Tzvika Geft and Dan Halperin , title =. 2021 , note =

    2021

  21. [21]

    2023 , note =

    Tzvika Geft and Noam Geller and Dan Halperin , title =. 2023 , note =

    2023

  22. [22]

    Agarwal and Mark de Berg and Benjamin Holmgren and Alex Steiger and Martijn Struijs , title =

    Pankaj K. Agarwal and Mark de Berg and Benjamin Holmgren and Alex Steiger and Martijn Struijs , title =. SoCG , series =

  23. [23]

    Kiril Solovey and Dan Halperin , title =. Int. J. Robotics Res. , volume =

  24. [24]

    and Schwartz, Jacob Theodore and Sharir, Micha , journal=

    Hopcroft, John E. and Schwartz, Jacob Theodore and Sharir, Micha , journal=. On the Complexity of Motion Planning for Multiple Independent Objects. 1984 , publisher=

    1984

  25. [25]

    Spirakis and Chee

    Paul G. Spirakis and Chee. Strong. Inf. Process. Lett. , volume =

  26. [26]

    Hearn and Erik D

    Robert A. Hearn and Erik D. Demaine , title =. Theor. Comput. Sci. , volume =

  27. [27]

    Wessel van der Heijden and Irina Kostitsyna and Lloyd E

    Thomas Brocken and G. Wessel van der Heijden and Irina Kostitsyna and Lloyd E. Lo. Multi-Robot Motion Planning of k-Colored Discs Is

  28. [28]

    Reconfigurations in Graphs and Grids , journal =

    Gruia C. Reconfigurations in Graphs and Grids , journal =

  29. [29]

    Mouawad and Naomi Nishimura , title =

    Alexandre Cooper and Stephanie Maaz and Amer E. Mouawad and Naomi Nishimura , title =

  30. [30]

    Adrian Dumitrescu and Minghui Jiang , title =. Comput. Geom. , volume =

  31. [31]

    2015 , publisher=

    Parameterized algorithms , author=. 2015 , publisher=

    2015

  32. [32]

    Bruno Courcelle , title =. Inf. Comput. , volume =

  33. [33]

    Bodlaender , title =

    Hans L. Bodlaender , title =. Theor. Comput. Sci. , volume =

  34. [34]

    SoCG , series =

    Bahareh Banyassady and Mark de Berg and Karl Bringmann and Kevin Buchin and Henning Fernau and Dan Halperin and Irina Kostitsyna and Yoshio Okamoto and Stijn Slot , title =. SoCG , series =

  35. [35]

    Matthew Turpin and Nathan Michael and Vijay Kumar , title =

  36. [36]

    International Conference on Fun with Algorithms , pages=

    Computational complexity of two-dimensional platform games , author=. International Conference on Fun with Algorithms , pages=. 2010 , organization=

    2010

  37. [37]

    Demaine and Alan Guo and Giovanni Viglietta , title =

    Greg Aloupis and Erik D. Demaine and Alan Guo and Giovanni Viglietta , title =. Theor. Comput. Sci. , volume =

  38. [38]

    Jonathan Gabor and Aaron Williams , title =

  39. [39]

    2020 , school=

    A framework for proving the computational intractability of motion planning problems , author=. 2020 , school=

    2020

  40. [40]

    Coulombe and Erik D

    Zachary Abel and Jeffrey Bosboom and Michael J. Coulombe and Erik D. Demaine and Linus Hamilton and Adam Hesterberg and Justin Kopinsky and Jayson Lynch and Mikhail Rudoy and Clemens Thielen , title =. Theor. Comput. Sci. , volume =

  41. [41]

    Wilfong , title =

    Gordon T. Wilfong , title =. Ann. Math. Artif. Intell. , volume =

  42. [42]

    Rolf H. M. Scheduling with

  43. [43]

    Pavel Surynek , title =

  44. [44]

    Demaine and S

    Erik D. Demaine and S. Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch , journal =

  45. [45]

    Jacopo Banfi and Nicola Basilico and Francesco Amigoni , title =

  46. [46]

    Tovey and Guni Sharon and T

    Hang Ma and Craig A. Tovey and Guni Sharon and T. K. Satish Kumar and Sven Koenig , title =

  47. [47]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =

  48. [48]

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. J. Comput. Syst. Sci. , volume =

  49. [49]

    Lower bounds based on the Exponential Time Hypothesis , journal =

    Daniel Lokshtanov and D. Lower bounds based on the Exponential Time Hypothesis , journal =

  50. [50]

    Kanj and Stefan Szeider , title =

    Ronald de Haan and Iyad A. Kanj and Stefan Szeider , title =. J. Artif. Intell. Res. , volume =

  51. [51]

    1982 , timestamp =

    David Lichtenstein , title =. 1982 , timestamp =

    1982

  52. [52]

    Knuth and Arvind Raghunathan , title =

    Donald E. Knuth and Arvind Raghunathan , title =. 1992 , timestamp =

    1992

  53. [53]

    Mark de Berg and Amirali Khosravi , title =

  54. [54]

    Time and Space Bounds for Planning , journal =

    Christer B. Time and Space Bounds for Planning , journal =

  55. [55]

    Machines , volume=

    Heuristics and Rescheduling in Prioritised Multi-Robot Path Planning: A Literature Review , author=. Machines , volume=. 2023 , publisher=

    2023

  56. [56]

    Kanj and Andrew Youngdahl , title =

    Eduard Eiben and Jonathan Gemmell and Iyad A. Kanj and Andrew Youngdahl , title =

  57. [57]

    Refining complexity analyses in planning by exploiting the exponential time hypothesis , journal =

    Meysam Aghighi and Christer B. Refining complexity analyses in planning by exploiting the exponential time hypothesis , journal =

  58. [58]

    CoRR , volume =

    Jingjin Yu , title =. CoRR , volume =

  59. [59]

    Workshop on the Algorithmic Foundations of Robotics,

    Jingjin Yu and Daniela Rus , title =. Workshop on the Algorithmic Foundations of Robotics,

  60. [60]

    Miller and Paul G

    Daniel Kornhauser and Gary L. Miller and Paul G. Spirakis , title =

  61. [61]

    Stefano Ardizzoni and Irene Saccani and Luca Consolini and Marco Locatelli and Bernhard Nebel , title =. J. Artif. Intell. Res. , volume =

  62. [62]

    American Journal of Mathematics , volume=

    Notes on the “15” puzzle , author=. American Journal of Mathematics , volume=. 1879 , publisher=

  63. [63]

    Journal of Combinatorial Theory, Series B , volume=

    Graph puzzles, homotopy, and the alternating group , author=. Journal of Combinatorial Theory, Series B , volume=. 1974 , publisher=

    1974

  64. [64]

    LaValle , title =

    Jingjin Yu and Steven M. LaValle , title =

  65. [65]

    Yakovlev , title =

    Zain Alabedeen Ali and Konstantin S. Yakovlev , title =

  66. [66]

    Gilad Fine and Dor Atzmon and Noa Agmon , title =

  67. [67]

    Solving simultaneous target assignment and path planning efficiently with time-independent execution , journal =

    Keisuke Okumura and Xavier D. Solving simultaneous target assignment and path planning efficiently with time-independent execution , journal =

  68. [68]

    Yakovlev , title =

    Stepan Dergachev and Konstantin S. Yakovlev , title =

  69. [69]

    Pierre Le Bodic and Edward Lam , title =

  70. [70]

    Sturtevant and Glenn Wagner and Pavel Surynek , title =

    Ariel Felner and Roni Stern and Solomon Eyal Shimony and Eli Boyarski and Meir Goldenberg and Guni Sharon and Nathan R. Sturtevant and Glenn Wagner and Pavel Surynek , title =

  71. [71]

    Sturtevant and Ariel Felner and Sven Koenig and Hang Ma and Thayne T

    Roni Stern and Nathan R. Sturtevant and Ariel Felner and Sven Koenig and Hang Ma and Thayne T. Walker and Jiaoyang Li and Dor Atzmon and Liron Cohen and T. K. Satish Kumar and Roman Bart. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks , booktitle =

  72. [72]

    Studies in Complexity and Cryptography , series =

    Oded Goldreich , title =. Studies in Complexity and Cryptography , series =

  73. [73]

    Oded Goldreich , title =

  74. [74]

    Journal of Symbolic Computation , volume=

    The (n^2-1) -puzzle and related relocation problems , author=. Journal of Symbolic Computation , volume=. 1990 , publisher=

    1990

  75. [75]

    Demaine and Mikhail Rudoy , title =

    Erik D. Demaine and Mikhail Rudoy , title =. Theor. Comput. Sci. , volume =

  76. [76]

    Jingjin Yu , title =

  77. [77]

    SoCG , series =

    Eduard Eiben and Robert Ganian and Iyad Kanj , title =. SoCG , series =

  78. [78]

    Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan , title =

  79. [79]

    Bernhard Nebel , title =

  80. [80]

    Bernhard Nebel , title =. Artif. Intell. , volume =

Showing first 80 references.