Revisiting token sliding on chordal graphs

In this article, we revisit the complexity of the reconfiguration of independent sets under the token sliding rule on chordal graphs. In the \textsc{Token Sliding-Connectivity} problem, the input is a graph G and an integer k, and the objective is to determine whether the reconfiguration graph TSk(G) of G is connected. The vertices of TSk(G) are k-independent sets of G, and two vertices are adjacent if and only if one can transform one of the two corresponding independent sets into the other by sliding a vertex (also called a \emph{token}) along an edge. Bonamy and Bousquet [WG'17] proved that the \textsc{Token Sliding-Connectivity} problem is polynomial-time solvable on interval graphs but \NP-hard on split graphs. In light of these two results, the authors asked: can we decide the connectivity of TSk(G) in polynomial time for chordal graphs with \emph{maximum clique-tree degree} d? We answer this question in the negative and prove that the problem is \para-\NP-hard when parameterized by d. More precisely, the problem is \NP-hard even when d=4. We then study the parameterized complexity of the problem for a larger parameter called \emph{leafage} and prove that the problem is \co-\W[1]-hard. We prove similar results for a closely related problem called \textsc{Token Sliding-Reachability}. In this problem, the input is a graph G with two of its k-independent sets I and J, and the objective is to determine whether there is a sequence of valid token sliding moves that transform I into J.