Token sliding connectivity by clique-tree degree

Question 1 · arXiv:1605.00442

arXiv Question high confidence— first stated 2016-05-02

Authors: Marthe Bonamy, Nicolas Bousquet

Status disproved high confidence

Bonamy and Bousquet asked whether bounding the clique-tree degree D of a chordal graph restores polynomial tractability for deciding connectivity of TS_k(G). Adak, Nanoti, and Tale (arXiv:2502.12749, 2025) directly and negatively answer this: TS-Connectivity is co-NP-hard on chordal graphs of maximum clique-tree degree 4, and TS-Reachability is NP-hard already at degree 3. Together these results show that bounded clique-tree degree does not make the problem polynomial-time tractable.

Cited literature (1)

counterexample Revisiting Token Sliding on Chordal Graphs (2025)

Rajat Adak, Saraswati Girish Nanoti, Prafullkumar Tale · arXiv preprint · arXiv:2502.12749

Proves TS-Connectivity is co-NP-hard on chordal graphs of maximum clique-tree degree 4 (Theorem 1.1), directly and negatively answering Question 1 of arXiv:1605.00442.

Reviewer notes. The question asked whether fixing any constant D makes TS_k(G) connectivity polynomial on chordal graphs of clique-tree degree at most D. The 2025 paper arXiv:2502.12749 answers no: co-NP-hardness holds at D=4. The status d=2 and d=3 for TS-Connectivity specifically may remain open, but the question as posed (for 'any integers k, D') is answered negatively.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. For any integers $k$, $D$, for any chordal graph $G$ of clique-tree degree at most $D$, can the connectivity of $TS_k(G)$ be decided in polynomial time?

Context

Motivated by the contrast between the polynomial time result for interval graphs (clique-tree degree 1) and the co-NP-hardness for split graphs, the authors introduce the clique-tree degree of a chordal graph $G$ as the smallest maximum degree of a clique-tree of $G$, and ask whether bounding this parameter restores polynomial tractability.

Source paper

Token Sliding on Chordal Graphs
Marthe Bonamy, Nicolas Bousquet · 2016-05-02
https://arxiv.org/abs/1605.00442 PDF source