Consider a graph
G
with
n
vertices. On each vertex we place a box. The
n
vertices and
n
boxes are each numbered from 1 to
n
, and initially shuffled according to a permutation
π
. A single robot is ...given the task to sort these boxes. In every step, the robot can walk along an edge of the graph and can carry at most one box at a time. At a vertex, it may swap the box placed there with the box it is carrying. How many steps does the robot need to sort all the boxes? We present efficient algorithms that construct such a shortest sorting walk if
G
is a path or a tree, and we show that the problem is
NP
-complete for planar graphs. If we minimize the number of swaps in addition to the number of walking steps, it is
NP
-complete even if
G
is a tree.
PDF
