Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs

Duc A. Hoang, Ryuhei Uehara

Given two independent sets $I,J$ of a graph $G$, and imagine that a token (coin) is placed at each vertex of $I$. The Sliding Token problem asks if one could transform $I$ to $J$…