TreeJam — Feel the NP-Hardness of Pebble Motion

What's the real result?

Pebble Motion: pebbles sit on the vertices of a graph, one empty vertex ("hole") lets you slide a neighboring pebble into it — one pebble, one move, one adjacent empty vertex at a time. The goal: reach a target arrangement using the fewest total moves.

Whether this is efficiently solvable on trees was a decades-old open question. This paper (Tzvika Geft, arXiv:2606.06686) resolves it: Pebble Motion is NP-hard on trees — even though trees are about the simplest connected graphs there are.

It goes further: the 2-colored variant, where pebbles only need to be distinguished by color (not individual identity — any red pebble may end on any target-red vertex), is proven NP-hard here too. The paper states this is the first-ever hardness result for 2-colored Pebble Motion on any graph class. Both results (and the labeled/full-identity case) hold under all three standard objectives the paper considers: total distance, makespan, and flowtime.

The hard instances the reduction builds live on subdivided stars — a single center vertex with several straight branches ("legs"), each subdivided into a chain of extra vertices. Nothing exotic: just a star with its edges cut into segments. The proof also connects Pebble Motion to a "Stack Rearrangement" problem, shown NP-hard along the way.

Below: drag a colored pebble onto an adjacent empty (dashed) node to move it toward the target layout shown underneath, while a real brute-force solver races the exact same instance in your browser.

The "~10–12 pebbles" choke point is this demo's empirical observation of brute-force search speed on your machine, not a number stated in the paper — the paper's contribution is the asymptotic NP-hardness proof, not a specific constant.

Tree shape balanced

easy (few branches) → paper's subdivided star

Pebble count 10

amber band ≈ where brute force typically starts to choke

Your moves: 0

Nodes: –

Legs: –

Colorings possible: –

Current — drag a pebble onto a dashed empty node

Target — reach this coloring

color A color B empty vertex