Back to Search
Start Over
Galactic token sliding.
- Source :
-
Journal of Computer & System Sciences . Sep2023, Vol. 136, p220-248. 29p. - Publication Year :
- 2023
-
Abstract
- Given a graph G and two independent sets I s and I t of size k , the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets that transforms I s to I t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G , the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the Token Jumping problem is fixed-parameter tractable (for parameter k) when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere dense graphs. As for the Token Sliding problem, almost nothing is known. We remedy this situation by showing that Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INDEPENDENT sets
*DENSE graphs
*SPARSE graphs
*PLANAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 136
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 163699488
- Full Text :
- https://doi.org/10.1016/j.jcss.2023.03.008