License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.39
URN: urn:nbn:de:0030-drops-173244
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17324/
Go to the corresponding LIPIcs Volume Portal


Agrawal, Akanksha ; Hait, Soumita ; Mouawad, Amer E.

On Finding Short Reconfiguration Sequences Between Independent Sets

pdf-format:
LIPIcs-ISAAC-2022-39.pdf (0.8 MB)


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 fixed-parameter 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 fixed-parameter tractable for parameter k + š“ + d on d-degenerate 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 2-degenerate 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:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17324},
  URN =		{urn:nbn:de:0030-drops-173244},
  doi =		{10.4230/LIPIcs.ISAAC.2022.39},
  annote =	{Keywords: Token sliding, token jumping, fixed-parameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}

Keywords: Token sliding, token jumping, fixed-parameter 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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI