Paperlane

no. 16 · Tuesday 17 November 2026

Independent set reconfiguration is hard at treewidth four

Hussein Abbas, Haydar Hamieh, Amer E. Mouawad and Ali Slim

math.CO · via cs.CC

Abstract

Independent Set Reconfiguration asks whether one of two given independent sets of equal size can be transformed into the other by moving one token at a time while keeping the occupied vertices independent. In token sliding, a token moves along an edge. In token jumping, it may move to any unoccupied vertex. For both rules, the problem is solvable in polynomial time on trees and is PSPACE-complete on graphs of treewidth at most $c$ for some fixed constant $c$. For each rule, the smallest treewidth bound that suffices for hardness has long been open. We narrow this gap by proving that both versions are NP-hard on graphs of treewidth four.

fields
Combinatorics
pdf ↗ page arXiv:2611.20205 ↗