Galactic Token Sliding

Abstract

Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets that transforms I_s to I_t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the Token Jumping problem is fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere-dense graphs. As for the Token Sliding problem almost nothing is known. We remedy this situation by showing that Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number.