A linear upper bound on the number of moves required for independent set reconfiguration with two sliding tokens
We consider the problem of shifting two tokens placed on nonadjacent vertices $u,v$ of a graph $G$ on $n$ vertices to two nonadjacent vertices $u',v'$ of $G$ using a sequence of token movements. In each step, a token is moved from the vertex it is on to a neighbour of that vertex, ensuring that the tokens remain on nonadjacent vertices after this move. We answer a question of Briański, Felsner, Hodor, and Micek [``Reconfiguring Independent Sets on Interval Graphs'', MFCS 2021] by showing that if the two tokens can be moved from their initial position to their final position, then it can be…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.13130
curl -X POST /api/v1/records/arxiv/2608.13130/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.13130/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'