# Introduction to Reconfiguration
## 4 Analysis Using Graph Classes for Independent Set  
In this section, we focus on the complexity of reachability of Independent Set Reconfiguration for various choices of graph classes and reconfiguration steps. The problem was proposed as a natural extension of token-sliding puzzles with the added constraint that all tokens form an _independent set_ (a subset of the vertices such that there is no edge between any pair of vertices in the set) [16]. Early results established the PSPACE-completeness of the problem under TS [16] and TAR [4]. Moreover, it was shown that there exists a reconfiguration sequence under TJ using \(k\) tokens if and only if there exists a sequence under TAR for bound \(k-1\), proving the equivalence of TJ and TAR for both reachability and shortest transformation [17]. Subsequent (and ongoing) research has focused on the question of the boundaries between tractability and intractability for the source problem based on various graph classes, both to determine whether the boundaries are the same for the source problem and for reachability, and to determine whether the boundaries for reachability are the same for both TS and TAR/TJ. Analyses of this type have also been considered for other problems for which reachability is PSPACE-complete on general graphs, including Clique Reconfiguration [53], Cluster Vertex Deletion Reconfiguration [53], Dominating Set Reconfiguration [50], and Vertex Cover Reconfiguration (discussed in more detail in Section 5). Figure 5 and Table 1 represent the results known so far. For both TS and TAR/TJ, there exist classes of graphs (such as perfect graphs and graphs of bounded bandwidth) for which the source problem can be solved in polynomial time, but reachability is PSPACE-complete. Although this makes clear that the dividing lines are not the same for the source problem and for reachability, it remains to be determined exactly where and why the boundaries diverge. Similarly, the result on bipartite graphs shows that boundaries are not identical for TS and TAR/TJ, but still leaves open the underlying cause  
Figure 4: Arrows depict inclusion relations among classes of graphs. of the difference, as well as its extent. Restriction to even-hole-free graphs is also of interest, as the complexity is unknown for both the source problem and under TS, but polynomial-time algorithms are possible under TAR/TJ. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Class** & **Source** & **TS** & **TAR/TJ** \\ \hline planar (of degree 3) & NP-complete & PSPACE-complete [17] & PSPACE-complete [17] \\ even-hole-free &? &? & P [17; 28; 54] \\ perfect & P & PSPACE-complete [17] & PSPACE-complete [17] \\ cograph & P & P [17] & P [42; 55] \\ chordal & P &? & P (since even-hole-free) \\ split & P & co-NP-hard [56] & P (since even-hole-free) \\ interval & P & P [56] & P (since even-hole-free) \\ claw-free & P & P [57] & P [57] \\ proper interval & P & P [58] & P (since even-hole-free) \\ caterpillar & P & P [58] & P (since even-hole-free) \\ tree & P & P [59] & P (since even-hole-free) \\ bipartite & P & PSPACE-complete [52] & NP-complete [52] \\ bipartite permutation & P & P [60] &? \\ bipartite distance hereditary & P & P [60] &? \\ block & P & P [61; 62] &? \\ bounded treewidth & P & PSPACE-complete [47] & PSPACE-complete [47] \\ bounded pathwidth & P & PSPACE-complete [47] & PSPACE-complete [47] \\ bounded bandwidth & P & PSPACE-complete [47] & PSPACE-complete [47] \\ cactus & P & P [61; 63] & P [54] \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Results on reachability for Independent Set Reconfiguration; question marks indicate problems for which there are no known complexity results. Figure 5: Complexity of reachability for Independent Set Reconfiguration; graph classes are divided by complexity for the source problem (solid lines), TAR/TJ (dotted lines), and TS (dashed lines). The dotted-and-dashed line is a dividing line for both TAR/TJ and TS. Results on Independent Set Reconfiguration have not been confined to reachability.