Title: Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs,
Abstract: 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$ via a sequence of elementary steps, where each step
requires sliding a token from one vertex to one of its neighbors so that the
resulting set of vertices where tokens are placed remains independent. This
problem is $\mathsf{PSPACE}$-complete even for planar graphs of maximum degree
$3$ and bounded-treewidth. In this paper, we show that Sliding Token can be
solved efficiently for cactus graphs and block graphs, and give upper bounds on
the length of a transformation sequence between any two independent sets of
these graph classes. Our algorithms are designed based on two main
observations. First, all structures that forbid the existence of a sequence of
token slidings between $I$ and $J$, if exist, can be found in polynomial time.
A sufficient condition for determining no-instances can be easily derived using
this characterization. Second, without such forbidden structures, a sequence of
token slidings between $I$ and $J$ does exist. In this case, one can indeed
transform $I$ to $J$ (and vice versa) using a polynomial number of
token-slides.