  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 problem is to determine whether there exists a sequence
of independent sets which transforms I_b into I_r so that each independent set
in the sequence results from the previous one by sliding exactly one token
along an edge in the graph. The sliding token problem is one of the
reconfiguration problems that attract the attention from the viewpoint of
theoretical computer science. The reconfiguration problems tend to be
PSPACE-complete in general, and some polynomial time algorithms are shown in
restricted cases. Recently, the problems that aim at finding a shortest
reconfiguration sequence are investigated. For the 3SAT problem, a trichotomy
for the complexity of finding the shortest sequence has been shown, that is, it
is in P, NP-complete, or PSPACE-complete in certain conditions. In general,
even if it is polynomial time solvable to decide whether two instances are
reconfigured with each other, it can be NP-complete to find a shortest sequence
between them. Namely, finding a shortest sequence between two independent sets
can be more difficult than the decision problem of reconfigurability between
them. In this paper, we show that the problem for finding a shortest sequence
between two independent sets is polynomial time solvable for some graph classes
which are subclasses of the class of interval graphs. More precisely, we can
find a shortest sequence between two independent sets on a graph G in
polynomial time if either G is a proper interval graph, a trivially perfect
graph, or a caterpillar. As far as the authors know, this is the first
polynomial time algorithm for the shortest sliding token problem for a graph
class that requires detours.
