# Introduction to Reconfiguration
## 3 Tools for Proving the Complexity of Reachability
For a more general result, such as on graph problems, one might try to identify a class of graphs for which reachability is tractable for a large class of source problems. Formal definitions of graph classes and properties mentioned without accompanying citations can be found in a textbook on graph theory [41]. As many results are more easily obtained on simple graphs such as paths and trees, one approach is to try to generalize results by considering classes of graphs that contain paths and trees (Figure 4). Paths and trees are _bipartite_ (properly colorable using two colors), _planar_ (embeddable on the plane without any edges crossing), and _chordal_ (containing no induced cycle on more than three vertices). Various graph classes are characterized by various width measures, such as _pathwidth_ and _treewidth_ (measures of how path-like or tree-like a graph is); one can generalize from paths (with pathwidth one) and trees (with treewidth one) to graphs of pathwidth \(k\) or treewidth \(k\) for a given constant \(k\). Such graphs retain useful properties, such as the solving of various problems using dynamic programming. Other graph parameters to be discussed later include _bandwidth_ (the minimum over all mappings \(f\) of the vertices to the set of natural numbers of the maximum of \(|f(u)-f(v)|\) over all edges \(uv\) in the graph), and _modular-width_[42]. The _contracted solution graph method_ has been proposed as a general method for developing algorithms by compacting the information in the reconfiguration graph and then applying dynamic programming, using tree decompositions. The method has been used for algorithms for Shortest Path Reconfiguration on planar graphs [43], List Coloring Reconfiguration on caterpillars [44], and \(k\)-Coloring Reconfiguration on \((k-2)\)-connected chordal graphs [45]. The technique led to a conjecture that treewidth could be exploited to obtain algorithms. Instead, a general technique was developed to show the PSPACE-hardness of reachability for instances of bounded bandwidth. Because a graph of bandwidth \(b\) has pathwidth and treewidth at most \(b\)[46], the use of treewidth in forming algorithms is limited. [PERSON] noted that dynamic programming has also been effectively used in solving reachability of Independent Set Reconfiguration for cographs [42]; as these are graphs of bounded modular-width, there may be a general method possible for graphs of bounded modular-width. It remains to be seen whether general results on reachability are possible for particular classes of graphs. Figure 3: OR and AND gates in an NCL machine. The result on bandwidth was proved using \(H\)-Word Reconfiguration, where given an alphabet and a binary relation between symbols, an \(H\)-_word_ is a word in which each pair of consecutive symbols is in the relation. [PERSON] [47] proved the PSPACE-completeness of the reachability problem, where the reconfiguration step is changing a single symbol, based on the classic proof of undecidability for general Thue systems [48]. Using this result, the following reachability problems were shown to be PSPACE-complete for graphs of bounded bandwidth: Shortest Path [47], \(k\)-Coloring [47], List Coloring [47], Independent Set [47], Vertex Cover [49], Feedback Vertex Set [49], Odd Cycle Transversal [49], Induced Forest [49], Induced Bipartite Subgraph [49], and Dominating Set [50]. In investigations of the parameterized complexity (defined in Section 5) of NCL under the parameters treewidth, maximum degree, and length of the reconfiguration sequence, \(H\)-Word Reconfiguration has been used to strengthen the framework to remain PSPACE-complete for graph of bounded bandwidth [51]. Moreover, \(H\)-Word Reconfiguration has been generalized to Even/Odd Word Reconfiguration, in which even and odd positions can be treated independently; this variant has been used for proving the PSPACE-completeness of reachability for Independent Set Reconfiguration under TS for bipartite graphs [52].