A linear-time algorithm for the feasibility of pebble motion on trees

We consider the following pebble motion problem. We are given a tree T with n vertices and two arrangements R and S of k < n distinct pebbles numbered 1,..., k on distinct vertices of the tree. Pebbles can move along edges of T provided that at any given time at most one pebble is traveling along an edge and each vertex of T contains at most one pebble. We are asked the fo llowing question: Is arrangement S reachable from R? We present an algorithm that, on input two arrangements of k pebbles on a t ree with n vertices, decides in time O(n) whether the two arrangements are reachable from one another. We also give an algorithm that, on input two re achable configurations, returns a sequence of moves that transforms one con figuration into the other. The pebble motion problem on trees has various applications including memor y management in distributed systems, robot motion planning, and deflection routing.