2025/02/18 by Adak, Rajat, Nanoti, Saraswati Girish, Tale, Prafullkumar
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.12749
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 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 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 TSk(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 \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 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.