← 研踪 PaperTrailarXiv:2503.20550 · v8
Structural Origins of Cubic Complexity in Pebble Motion
首次提交 2025-03-26 21:46
版本更新 2026-11-02 23:59
雷达观测 2026-11-04 23:41
摘要
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 $\mathrm{O}(N^2\log N)$, constructible in time linear in its length. This is the first $\mathrm{o}(N^3)$ upper bound for PMP on trees. We then extend the method to general graphs. When $2\le N-n=\mathrm{O}(1)$, every instance on a feasible puzzle admits a solution of length $\mathrm{O}(n\,\mathrm{CL}(G)\,\mathrm{D}(G))$, where $\mathrm{D}(G)$ is the diameter and $\mathrm{CL}(G)$ is the maximum length of a shortest cycle through a vertex; this recovers the classical $\mathrm{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 $\mathrm{O}(1)$ vertices, whereas two $Θ(N)$-cycles meeting at one vertex have complexity exactly $Θ(N^2\log N)$. We conjecture that the former construction essentially characterizes the cubic regime.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v8 · 2026-11-02 23:59 · 最新观测版本
Structural Origins of Cubic Complexity in Pebble Motion
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 $\mathrm{O}(N^2\log N)$, constructible in time linear in its length. This is the first $\mathrm{o}(N^3)$ upper bound for PMP on trees. We then extend the method to general graphs. When $2\le N-n=\mathrm{O}(1)$, every instance on a feasible puzzle admits a solution of length $\mathrm{O}(n\,\mathrm{CL}(G)\,\mathrm{D}(G))$, where $\mathrm{D}(G)$ is the diameter and $\mathrm{CL}(G)$ is the maximum length of a shortest cycle through a vertex; this recovers the classical $\mathrm{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 $\mathrm{O}(1)$ vertices, whereas two $Θ(N)$-cycles meeting at one vertex have complexity exactly $Θ(N^2\log N)$. We conjecture that the former construction essentially characterizes the cubic regime.
查看此版本解读 →查看此版本原文 ↗