Name
Abstract | ||
|---|---|---|
In the TOKEN SLIDING problem we are given a graph G and two independent sets I-s and I-t in G of size k >= 1. The goal is to decide whether there exists a sequence < I-1, I-2,...,I-l) of independent sets such that for all i is an element of {1, ...,l} the set I-i is an independent set of size k, I-1 = I-s, I-l = I-t and I-i Delta Ii+1 = {u, v} is an element of 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 I-s into I-t 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. [2], 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 based on the girth of the input graph. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/978-3-031-15914-5_5 | GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2022) |
Keywords | DocType | Volume |
token sliding, independent set, girth, combinatorial reconfiguration, parameterized complexity | Conference | 13453 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Valentin Bartier | 1 | 0 | 0.34 |
| Nicolas Bousquet | 2 | 0 | 0.34 |
| Jihad Hanna | 3 | 0 | 0.34 |
| Amer E. Mouawad | 4 | 0 | 0.34 |
| Sebastian Siebertz | 5 | 0 | 0.34 |