WorksComputer Science
Independent set reconfiguration is hard at treewidth four
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 for some fixed constant . 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.