{"id":"arxiv/2611.20205","url":"https://arxiv.org/abs/2611.20205","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"Independent set reconfiguration is hard at treewidth four","domain":"cs.CC","source":"arxiv","authors":["Hussein Abbas","Haydar Hamieh","Amer E. Mouawad","Ali Slim"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-15","reactions":{}}