Structural Origins of Cubic Complexity in Pebble Motion
math.CO, cs.CC, cs.DM
Submitted: 2025-03-26
Updated: 2026-11-10
License: http://creativecommons.org/licenses/by/4.0/
The gist: The pebble motion problem (PMP) asks whether one configuration of labeled pebbles on a graph can be transformed into another by moving pebbles to adjacent unoccupied vertices.
Abstract
The pebble motion problem (PMP) asks whether one configuration of labeled pebbles on a graph can be transformed into another by moving pebbles to adjacent unoccupied vertices. Kornhauser, Miller, and Spirakis proved that the worst-case shortest solution length on an N-vertex graph is Θ(N 3), but the graph structures responsible for this cubic behavior remained unclear. We first show that cubic complexity cannot occur on trees: every feasible instance on an N-vertex tree admits a solution sequence of length O(N squared N), constructible in time linear in its length. This is the first o(N 3) upper bound for PMP on trees. We then extend the method to general graphs. When 2 at most N-n= O(1), every instance on a feasible puzzle admits a solution of length O(n, CL(G), D(G)), where D(G) is the diameter and CL(G) is the maximum length of a shortest cycle through a vertex; this recovers the classical O(N 3/2) bound for square grids. We further show that any graph with worst-case shortest solution length Θ(N 3) has a unique biconnected component X of order Θ(N), while all structures attached through any one cut vertex of X have bounded total size. Moreover, X contains no cycle of unbounded sublinear order, and any two intersecting cycles of order Θ(N) share at least as many vertices as there are blanks. Finally, cubic complexity occurs when a cycle of order Θ(N) contains all but O(1) vertices, whereas two Θ(N) -cycles meeting at one vertex have complexity exactly Θ(N squared N). We conjecture that the former construction essentially characterizes the cubic regime.
Sources
- Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids
- MAPF-World: Action World Model for Multi-Agent Path Finding
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality