On finding short reconfiguration sequences between independent sets
| Autor: | Agrawal, Akanksha, Hait, Soumita, Mouawad, Amer E. |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
History Polymers and Plastics Discrete Mathematics (cs.DM) combinatorial reconfiguration Computational Complexity (cs.CC) Industrial and Manufacturing Engineering Token sliding Computer Science - Computational Complexity shortest reconfiguration sequence token jumping fixed-parameter tractability Computer Science - Data Structures and Algorithms FOS: Mathematics Theory of computation → Parameterized complexity and exact algorithms Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) Business and International Management Computer Science - Discrete Mathematics |
| DOI: | 10.48550/arxiv.2209.05145 |
| Popis: | 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. LIPIcs, Vol. 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), pages 39:1-39:14 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|