# A Linear Time Algorithm for the Feasibility of Pebble Motion on Graphs

arXiv: https://arxiv.org/abs/1301.2342 · HTML: https://mlsanity.com/paper/1301.2342/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2013.

## Built on by (most cited first, 1 of 1)

- [On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles](https://mlsanity.com/paper/2312.10887/) (2023)

## Abstract (arXiv)

Given a connected, undirected, simple graph G = (V, E) and p ≤ |V| pebbles labeled 1,..., p, a configuration of these p pebbles is an injective map assigning the pebbles to vertices of G. Let S and D be two such configurations. From a configuration, pebbles can move on G as follows: In each step, at most one pebble may move from the vertex it currently occupies to an adjacent unoccupied vertex, yielding a new configuration. A natural question in this setting is the following: Is configuration D reachable from S and if so, how? We show that the feasibility of this problem can be decided in time O(|V| + |E|).