Structural Analysis in Combinatorial Reconfiguration (SCoRe)

Combinatorial reconfiguration is a framework to study transformations between states of an object. Think about the Rubiks Cube. Each state represents an arrangement of colored stickers on the cube, and one state can be transformed to another by rotating its faces. The task in this case is to find the quickest way to go from an initial state (a scrambled cube) to a desired state (the solved cube where all stickers in each face have the same color). While puzzles like the Rubiks Cube are a rich source of reconfiguration problems, such problems also appear in a variety of other contexts, two of which are explored in this project. The first context is the k-Opt heuristic for the Travelling Salesman Problem (TSP). This problem asks for a shortest tour that visits a set of cities (and returns to the starting city). The k-Opt heuristic starts with an arbitrary tour and iteratively replaces up to k edges with alternative edges to shorten the tour. This is a core component of the Lin-Kerninghan algorithm, a widely used method for solving TSP. While the k-Opt heuristic performs well in practice, theoretically it can take a long time to finish, especially for k at least 5. The proposed project aims to fill in this gap: Can the theoretically long runtime also occur for k < 5? Are there any specific structural properties of the distances between the cities that allow the heuristic to run faster? If we are willing to sacrifice some solution quality, is there a way to modify the heuristic to speed up its execution? The second context considered in this project is related to the task of combinatorial generation: to list all objects that satisfy a given description. A classic example is generating all binary strings of length n, which can be done efficiently by the Binary Reflected Gray Code. An interesting property of this listing is that consecutive strings differ exactly by a single position. In broader terms, a Gray code refers to a listing where two consecutive elements differ by a small change. (In this case, the elements are the states in the reconfiguration framework, while the small changes are the transformations.) Although many Gray codes have been discovered, it is in fact a provably challenging task to find one in general. This project aims to deepen our understanding in the computability of Gray codes by addressing the following question: What structural properties should the set of objects have to guarantee efficient computation of a Gray code for it? The objects studied in this project will include strings, permutations, and graph structures, among others, all of which are fundamental to various fields of computer science.