Structural Origins of Cubic Complexity in Pebble Motion

Tomoki Nakamigawa, Tadashi Sakuma

The pebble motion problem (PMP) asks whether one configuration of labeled pebbles on a graph can be transformed into another by moving pebbles to adjacent unoccupied vertices. It i…