Pebble motion problems

The general form of the pebble motion problem is Pebble Motion on Graphs^[1] formulated as follows:

Let ${\displaystyle G=(V,E)}$  be a graph with ${\displaystyle n}$  vertices. Let ${\displaystyle P=\{1,\ldots ,k\}}$  be a set of pebbles with ${\displaystyle k<n}$ . An arrangement of pebbles is a mapping ${\displaystyle S:P\rightarrow V}$  such that ${\displaystyle S(i)\neq S(j)}$  for ${\displaystyle i\neq j}$ . A move ${\displaystyle m=(p,u,v)}$  consists of transferring pebble ${\displaystyle p}$  from vertex ${\displaystyle u}$  to adjacent unoccupied vertex ${\displaystyle v}$ . The Pebble Motion on Graphs problem is to decide, given two arrangements ${\displaystyle S_{0}}$  and ${\displaystyle S_{+}}$ , whether there is a sequence of moves that transforms ${\displaystyle S_{0}}$  into ${\displaystyle S_{+}}$ .

Common variations on the problem limit the structure of the graph to be:

• a tree^[2]
• a square grid,^[3]
• a bi-connected graph.^[4]

Another set of variations consider the case in which some^[5] or all^[3] of the pebbles are unlabeled and interchangeable.

Other versions of the problem seek not only to prove reachability but to find a (potentially optimal) sequence of moves (i.e. a plan) which performs the transformation.

Finding the shortest solution sequence in the pebble motion on graphs problem (with labeled pebbles) is known to be NP-hard^[6] and APX-hard.^[3] The unlabeled problem can be solved in polynomial time when using the cost metric mentioned above (minimizing the total number of moves to adjacent vertices), but is NP-hard for other natural cost metrics.^[3]