Delphi.science

Independent set reconfiguration is hard at treewidth four

Source: arxiv.org/abs/2611.20205

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

arXivarxiv/2611.20205Nov 15, 2026cs.CCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.20205
curl -X POST /api/v1/records/arxiv/2611.20205/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.20205/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'