Shortest Reconfiguration Sequence for Sliding Tokens on Spiders

Duc A. Hoang, Amanj Khorramian, Ryuhei Uehara

Suppose that two independent sets $I$ and $J$ of a graph with $|I|=|J|$ are given, and a token is placed on each vertex in $I$. The Sliding Token problem is t…