# The Independent Set Reconfiguration (ISR) Problem

## Definition

- Input
- an undirected graph \(G=(V, E)\).
- two independent sets of \(G\):
**start state**\(I_s\) and**target state**\(I_t\) where \(|I_s| = |I_t|\) holds.

- Output
- existence (yes or no) of a reconfiguration sequence from \(I_s\) to \(I_t\) under the reconfiguration rule (token jump).
- in case of yes, one reconfiguration sequence.

- Reconfiguration sequence under the token jump rule
- An independent set of \(G\) is a set of vertices in \(G\) such that no two vertices are adjacent.
- Suppose that a token is placed on each vertex in an independent set of \(G\).
- A
**reconfiguration sequence**from \(I_s\) to \(I_t\) under the**token jump rule**is a sequence of independent sets of \(G\) which transforms \(I_s\) into \(I_t\) so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. - The
**length**of a reconfiguration sequence is the number of independent sets (including \(I_s\) and \(I_t\))**minus one**, that is, the number of token moves.

## Example of input

- undirected graph \(G\)
- \(V=\{1,2,3,4,5,6,7\}\)
- \(E=\{\{1,2\},\{1,3\},\{2,7\},\{3,4\},\{3,5\},\{4,6\},\{5,6\}\}\)

- start state \(I_s = \{3,6,7\}\)
- target state \(I_t = \{4,5,7\}\)

It is illustrated as follows.

start state |
target state |

## Example of output

- existence of a reconfiguration sequence
- yes

- a reconfiguration sequence
- \((\{3,6,7\},\{1,6,7\},\{1,5,7\},\{4,5,7\})\)

- the length of this reconfiguration sequence
- 3 (the number of independent set
**minus one**)

- 3 (the number of independent set

It is illustrated as follows:

\(I_0 = I_s\) | \(I_1\) | \(I_2\) | \(I_3 = I_t\) |