Shortest Reconfiguration of Sliding Tokens on a Caterpillar

Takeshi Yamada, Ryuhei Uehara

Suppose that we are given two independent sets I_b and I_r of a graph such that |I_b|=|I_r|, and imagine that a token is placed on each vertex in |I_b|. Then, the sliding token pro…