Abstract
Assume we are given a graph G, two independent sets S and T in G of size k ≥ 1, and a positive integer ? ≥ 1. The goal is to decide whether there exists a sequence ⟨ I₀, I₁, ..., I_? ⟩ of independent sets such that for all j ∈ {0,…,?1} the set I_j is an independent set of size k, I₀ = S, I_? = T, and I_{j+1} is obtained from I_j by a predetermined reconfiguration rule. We consider two reconfiguration rules, namely token sliding and token jumping. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most ? steps that transforms S into T, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex (while maintaining independence). In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph (as long as we maintain independence). Both TSO and TJO are known to be fixedparameter tractable when parameterized by ? on nowhere dense classes of graphs. In this work, we investigate the boundary of tractability for sparse classes of graphs. We show that both problems are fixedparameter tractable for parameter k + ? + d on ddegenerate graphs as well as for parameter M + ? + Δ on graphs having a modulator M whose deletion leaves a graph of maximum degree Δ. We complement these result by showing that for parameter ? alone both problems become W[1]hard already on 2degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. [Daniel Lokshtanov et al., 2020]. Finally, we show as a side result that using such families we can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem (a.k.a. Token Jumping) parameterized by k on both degenerate and nowhere dense classes of graphs.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2022.39,
author = {Agrawal, Akanksha and Hait, Soumita and Mouawad, Amer E.},
title = {{On Finding Short Reconfiguration Sequences Between Independent Sets}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {39:139:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17324},
URN = {urn:nbn:de:0030drops173244},
doi = {10.4230/LIPIcs.ISAAC.2022.39},
annote = {Keywords: Token sliding, token jumping, fixedparameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}
Keywords: 

Token sliding, token jumping, fixedparameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence 
Collection: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 