2022/05/02 by Valentin Bartier, Nicolás Bousquet, Bartier, Valentin +7 · 2 citations
Computer Science · #Advanced Graph Theory Research #semigroups and automata theory #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2205.01009
In the Token Sliding problem we are given a graph G and two independent sets Is and It in G of size k ≥ 1. The goal is to decide whether there exists a sequence ⟨ I1, I2, …, I_ℓ ⟩ of independent sets such that for all i ∈ \1,…, ℓ\ the set Ii is an independent set of size k, I1 = Is, I_ℓ = It and Ii \triangle Ii + 1 = \u, v\ ∈ E(G). Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms Is into It where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al., the problem is W[1]-hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant p ≥ 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.