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

CREATORRajat Adak, Saraswati Girish Nanoti, Prafullkumar Tale
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12749

Browse the full library · About the Tower of Babel