Revisiting Token Sliding on Chordal Graphs
Rajat Adak, Saraswati Girish Nanoti, Prafullkumar Tale · 2025
Read Revisiting Token Sliding on Chordal Graphs by Rajat Adak, Saraswati Girish Nanoti, Prafullkumar Tale (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12749.txt.
Description
Rajat Adak, Saraswati Girish Nanoti, and Prafullkumar Tale revisit token sliding on chordal graphs in a 2025 paper. Tokens sit on a graph's corners, no two adjacent. A move slides one token along an edge to a free corner. The question is whether any layout of a set size can be reached from any other by such slides.
For interval graphs the answer can be computed fast; for split graphs the question is NP-hard. Chordal graphs sit between the two, and their case was left open by the earlier work. The team take up that gap, and weigh where the chordal case falls on the line between easy and hard.
Catalog record
| CREATOR | Rajat Adak, Saraswati Girish Nanoti, Prafullkumar Tale |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12749