A linear upper bound on the number of moves required for independent set reconfiguration with two sliding tokens

Abstract

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^{\prime },v^{\prime }$ 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 done using at most $4n$ moves.

10 pages, 2 figures