Skip to content

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