{"id":"1760f973-4e2b-4e2f-b722-18942ae72468","arxiv_id":"2606.06686","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.","lead":"The paper proves NP-hardness for labeled and 2-colored multi-agent path finding on trees under distance, makespan, and flowtime objectives, resolving the long-open complexity of pebble motion on trees. A smart generalist might read it to understand why exact optimal planning remains intractable even on the simplest tree graphs used in robotics.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"Correctness of reductions from Stack Rearrangement to MAPF on trees (objectives and feasibility)","rationale":"The reader's weakest_assumption directly names the load-bearing step. The abstract supplies no reduction details, so the technical correctness of objective preservation cannot be checked; this is the precise point where the argument could fail. No other internal inconsistency is visible from the given material.","tokens_in":1787,"tokens_out":343,"duration_ms":20061,"concrete_test":"Take an optimal Stack Rearrangement instance of cost K; apply the claimed reduction to produce the corresponding MAPF instance on the tree; verify that every feasible stack solution of cost K maps to a feasible MAPF solution whose objective equals f(K) (for the appropriate f per objective) and that every MAPF solution of cost f(K) maps back to a stack solution of cost K, with no spurious collisions or extra moves introduced by the tree embedding.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims rest on first proving NP-hardness of Stack Rearrangement, then giving polynomial reductions from it to labeled and 2-colored MAPF on trees (including the one-move-at-a-time pebble model) for distance, makespan, and flowtime. These reductions must map feasible stack sequences to feasible non-colliding paths on the tree while preserving the exact objective value (or an affine transformation thereof). If the construction fails to enforce that colored agents remain interchangeable only within colors, or if it introduces extra moves/collisions not present in the stack instance (especially on subdivided stars), then the NP-hardness transfers do not hold for all three objectives simultaneously.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1911,"tokens_out":466,"duration_ms":17353,"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":[{"comment":"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.","section":"Reduction sections (likely §4–§6)"},{"comment":"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.","section":"Stack Rearrangement hardness proof (likely §3)"}],"minor_comments":[{"comment":"Notation for the three objectives (distance, makespan, flowtime) should be introduced once with consistent symbols before the reductions are stated.","section":"Preliminaries"},{"comment":"Figure captions for the subdivided-star constructions should explicitly label which vertices correspond to stack positions versus routing paths.","section":"Figures illustrating reductions"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"partial","referee_comment":"[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."},{"response":"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_made":"no","referee_comment":"[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."}],"tokens_in":1438,"tokens_out":535,"duration_ms":24578,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The punchline is that this paper asserts NP-hardness for labeled and 2-colored MAPF on trees under distance, makespan, and flowtime, including the classical one-move-at-a-time pebble motion problem that had stayed open for decades. It also claims the first hardness for colored pebble motion on any graph class, already with two colors, and traces everything back to proving NP-hardness for Stack Rearrangement on subdivided stars.\n\nWhat stands out is the unifying framework: one source problem yields hardness across the variants and already on very simple trees. That is a clean way to strengthen earlier results without separate constructions for each objective.\n\nThe soft spot is exactly where the stress-test points: the reductions from Stack Rearrangement must map feasible stack sequences to collision-free paths while preserving the precise objective values (or a simple affine shift) and respecting color interchangeability. The abstract gives no reduction details or verification steps, so it is impossible to confirm that no extra moves or collisions are introduced on the tree. If those mappings hold, the results are solid; if they slip on even one objective, the transfer fails for the full set of claims.\n\nThis is for people working on complexity of motion planning and graph search problems. A reader who follows open cases in MAPF or pebble motion will want to see whether the reductions close the gaps. It deserves a serious referee to examine the constructions in detail.","headline":"Claims to settle long-open NP-hardness for MAPF and pebble motion on trees via a new Stack Rearrangement reduction, but the reductions need close checking for objective preservation.","tokens_in":2369,"tokens_out":365,"would_cite":true,"duration_ms":14944,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Optimal multi-agent motion on trees is NP-hard for both labeled and colored cases across all standard objectives.","keywords":["multi-agent path finding","pebble motion","NP-hardness","trees","stack rearrangement","motion planning on graphs"],"falsifier":"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.","tokens_in":2684,"feed_emoji":"","tokens_out":580,"duration_ms":22460,"temperature":0.7,"pith_summary":"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.","feed_headline":"Pebble motion on trees is NP-hard","feed_subtitle":"New proof links it to stack rearrangement and settles open questions for labeled and colored variants under distance, makespan and flowtime.","key_machinery":"A polynomial-time reduction from the NP-hard Stack Rearrangement problem to the various MAPF problems on trees that maintains the objective values.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Pebble motion on trees NP-hard via stack rearrangement","MAPF hardness on trees for labeled and 2-colored variants","Stack rearrangement NP-hard on subdivided stars","Open MAPF problems on trees settled as NP-hard"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The reductions from Stack Rearrangement to the MAPF variants on trees preserve both feasibility and the exact objective values.","fun_headline_variants_meta":{"raw":{"variants":["Pebble motion on trees NP-hard via stack rearrangement","MAPF hardness on trees for labeled and 2-colored variants","Stack rearrangement NP-hard on subdivided stars","Open MAPF problems on trees settled as NP-hard"]},"model":"grok-4.3","cost_usd":0.008038,"raw_usage":{"total_tokens":3611,"prompt_tokens":738,"num_sources_used":0,"completion_tokens":61,"cost_in_usd_ticks":80378000,"prompt_tokens_details":{"text_tokens":738,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2812,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":738,"tokens_out":61,"duration_ms":33987,"temperature":1.0,"reasoning_tokens":2812,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T00:58:11.807675+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}