The pebble motion problem starts with labeled pebbles placed on the vertices of a finite undirected simple graph and asks for a sequence of legal moves from one configuration to another. A legal move transfers one pebble to an adjacent vertex that is currently unoccupied, so collisions are avoided by construction. The problem is a basic graph-reconfiguration model, closely related to the fifteen puzzle and to multi-agent path finding. Its central complexity question is not only whether a target configuration is reachable, but also how many moves a shortest solution may require as a function of the board structure.
The main contribution is an output-sensitive algorithm showing that every feasible instance on an N-vertex tree admits a solution sequence of order N squared times log N. Together with the known quadratic lower bound, this reduces the unresolved gap for trees to a logarithmic factor and proves that the classical cubic phenomenon does not occur on trees. The paper then extends the approach to general graphs by applying the tree algorithm to breadth-first spanning trees, obtaining subcubic solution sequences for a broad class of instances. Finally, its structural analysis shows that cubic behavior can occur only under stringent conditions involving linearly many degree-two vertices on cycles of linear length, with each relevant cycle being the shortest cycle containing its corresponding vertex.
The tree algorithm decomposes a feasible instance into smaller subtree-based subproblems while controlling the size of long isthmuses, namely path-like bottlenecks whose edges and internal vertices have strong separation properties. Base procedures handle cases with ample blank space or bounded isthmus size by gathering pebbles, solving local rearrangements, and recombining the partial configurations. Structural lemmas construct subtrees of suitable sizes and support a recursive organization of the subproblem data, including a binary-tree-style database used in the complexity analysis. The general-graph framework chooses a breadth-first spanning tree and runs the tree machinery on it, while the additional graph edges provide alternative routes. A refined analysis uses graph diameter, shortest-cycle lengths, and the placement of degree-two vertices to relate the output length and running time to the instance structure.
The evidence supplied with the paper describes a theoretical validation rather than a conventional empirical benchmark study. Correctness and complexity are established through lemmas and theorems covering the base cases, subtree decomposition, recursive solution process, and extension from trees to general graphs. The square-grid example is used as an important application of the general framework, recovering a solution-length bound of order N to the three-halves power associated with that setting. The supplied excerpt does not provide dataset descriptions, implementation benchmarks, measured runtimes, or a numerical comparison against competing software, so empirical superiority and average-case behavior cannot be established from it.
The results indicate that worst-case difficulty is governed by structural bottlenecks rather than by the number of vertices alone. On trees, long path-like isthmuses can create substantial coordination costs, and if blank space is insufficient they may even make an instance infeasible, but they do not produce cubic solution complexity for feasible instances. In general graphs, cycles can offer useful detours, yet a large population of degree-two vertices arranged on long cycles can make those detours expensive to coordinate. The derived conditions sharply narrow the possible source of cubic behavior, although the supplied excerpt does not establish that every graph satisfying those conditions necessarily has a cubic shortest solution or that the conditions are sufficient. The paper also suggests that its techniques may improve MAPF procedures that use pebble-motion routines as core subroutines.
Pebble motion has been studied in discrete mathematics, 提案手順c theory, computational geometry, and artificial intelligence. The fifteen puzzle is a standard grid-based example, while related applications include memory allocation, warehouse robotics, traffic control, game AI, and certain biomedical diagnostic systems. Earlier work characterized feasibility in the single-blank case and established a polynomial-time feasibility test for general undirected graphs. Pebble-motion procedures are also used inside several MAPF approaches, making improvements in their solution length and running time potentially relevant beyond the abstract puzzle itself. A longstanding general upper bound of cubic order left open the question of which instances actually need that much work.
The input consists of a finite undirected graph, a set of labeled pebbles, unoccupied vertices, an initial configuration, and a goal configuration. Each move takes one pebble across an edge to an unoccupied neighboring vertex. The task is to produce a move sequence whenever the instance is feasible, while understanding the asymptotic length of the shortest such sequence. For general graphs, the classical worst-case upper bound is cubic in the number of vertices, while a quadratic lower bound is known in relevant settings. The paper asks for a sharper bound on trees and for a structural explanation of when cubic behavior can remain possible on general graphs.
For trees, the principal guarantee is a solution sequence of order N squared times log N for every feasible instance on an N-vertex board. The 提案手順s output-sensitive, so its computation time is analyzed in relation to the sequence that it explicitly produces, although the supplied excerpt omits the complete formulas and constants. For general graphs, a breadth-first spanning tree transfers the tree guarantee to a broad class of instances and yields subcubic outputs, including the square-grid bound of order N to the three-halves power. The structural restriction on possible cubic behavior requires linearly many degree-two vertices to lie on cycles of linear length, with each such cycle shortest among those containing the associated vertex.
The supplied evidence presents proof-based evaluation rather than a standard experimental section with datasets and measured trials. The 提案手順s checked analytically through base cases, decomposition lemmas, local rearrangement procedures, and a recursive assembly argument. The square grid serves as a theoretical case study showing how the general-graph construction recovers a known subcubic order. Exact graph sizes, random-instance distributions, hardware, software baselines, and empirical measurements are not included in the excerpt, so no claim about practical speed or average performance is supported by the supplied material.
Every feasible tree instance on N vertices has a constructible solution of order N squared times log N, improving the previously relevant cubic scale for trees. Since a quadratic lower bound is known, the tree result nearly determines the asymptotic optimum up to a logarithmic factor. Applying the method through breadth-first spanning trees produces subcubic sequences for a broad class of general-graph instances and recovers the square-grid order of N to the three-halves power. The analysis further confines possible cubic behavior to graphs containing a very specific arrangement of long cycles and degree-two vertices.
The paper resolves the long-standing tree case by showing that cubic complexity is not an unavoidable feature of feasible pebble motion on trees. Its decomposition gives a near-quadratic guarantee and an efficient way to generate the actual sequence of moves. The extension to general graphs distinguishes common, structurally manageable boards such as square grids from exceptional boards that may still support cubic behavior. More broadly, the work replaces a largely global worst-case view with a structural account based on bottlenecks, cycles, and low-degree corridors.
Several mathematical expressions and parameter definitions are missing from the supplied excerpt, so the exact running-time bounds, thresholds involving the number of blank vertices, and constant factors cannot be reconstructed safely. The excerpt also does not show whether the structural restriction is close to sufficient for constructing cubic lower-bound families, beyond stating it as a necessary restriction on possible cubic behavior. No implementation data, real-world MAPF evaluation, or comparison with concrete solver variants is supplied. Consequently, the theoretical guarantees should not be interpreted as measured practical speedups without consulting the complete paper and any accompanying code or experiments.
Pebble motion is a compact model of collision-free multi-agent rearrangement, and it underlies techniques used in MAPF. This paper matters because it both improves the asymptotic solution guarantee for trees and identifies a concrete structural source of exceptional difficulty in general graphs. The result explains why tree-like and grid-like boards can be easier than the broad cubic worst case, while also clarifying what a genuinely hard board must look like. These insights can guide structural instance classification, decomposition-based solver design, and the analysis of MAPF subroutines.
The paper is recommended for researchers in pebble motion, MAPF, graph reconfiguration, and asymptotic algorithm analysis. It is especially relevant to readers interested in tree decompositions, cut-vertex and isthmus structure, cycle-based detours, and output-sensitive construction algorithms. It is less suitable as a standalone source for empirical MAPF benchmarking because the supplied evidence contains no detailed datasets, implementation measurements, or controlled solver comparisons. Readers seeking those details should consult the complete paper rather than infer them from this excerpt.