{"id":"arxiv/2608.13130","url":"https://arxiv.org/abs/2608.13130","tags":["math.CO","cs.DM"],"score":0,"title":"A linear upper bound on the number of moves required for independent set reconfiguration with two sliding tokens","domain":"math.CO","source":"arxiv","authors":["Nived J. M.","Mathew C. Francis"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-13","reactions":{}}