Revisiting Token Sliding on Chordal Graphs

Abstract

In this article, we revisit the complexity of the reconfiguration of independent sets under the token sliding rule on chordal graphs. In the Token Sliding Connectivity problem, the input is a graph G and an integer k, and the objective is to determine whether the reconfiguration graph TS_k(G) of G is connected. The vertices of TS_k(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 token) along an edge. Bonamy and Bousquet [WG'17] proved that the 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 TS_k(G) in polynomial time for chordal graphs with maximum clique-tree degree d? We answer this question in the negative and prove that the problem is NP-hard even when d = 4. We then study the parameterized complexity of the problem for a larger parameter called leafage and prove that the problem is co-W[1]-hard. We prove similar results for a closely related problem called 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.