# 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)

It is illustrated as follows:    $$I_0 = I_s$$ $$I_1$$ $$I_2$$ $$I_3 = I_t$$