Reconfiguring a system (generally represented by a graph) means gradually transforming one configuration of the system to another configuration by modifying it in a slow and steady step-by-step manner. In the Shortest Path Reconfiguration (SPR) problem, we are given two shortest paths, and the goal is to transform one shortest path to the other by changing one vertex at a time, so that all the intermediate configurations are also shortest paths. SPR has many real-world applications like repaving roads in a systematic way, rerouting messages across a network of telecommunication towers, cargo container stowage on ships, train marshalling, and rerouting data packets across servers in a synchronous multiprocessor setting.
In this talk, we will show how one of these applications can be modelled by a specific class of graphs, and then we will solve SPR for that graph class. We will also show that if we are allowed to change two vertices at a time, then SPR becomes PSPACE-complete, even for a graph class for which SPR is known to be solvable in polynomial time when we are allowed to change only one vertex at a time. This is joint work with Agastya Vibhuti Jha, Manish Kumar and Abhiruk Lahiri (https://arxiv.org/abs/2112.07499).
Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
