Please note: This PhD seminar will take place online.
Stephanie Maaz, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Naomi Nishimura, Amer E. Mouawad
The goal of this talk is to introduce the solution discovery framework and discuss a joint work with Mario Grobler, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, and Sebastian Siebertz on the kernelization complexity of some solution discovery problems. Each of those solution discovery problems relates to one vertex (edge) subset source problem Π on graphs. It also takes as input an initial configuration of tokens on the vertices (edges) of an input graph G together with a budget b, and asks whether we can transform the given configuration into a feasible solution of Π on G with at most b modification steps. Here, each modification step consists of sliding a token to an adjacent vertex (edge). Our work focused on foundational source problems such as Vertex Cover, Independent Set, Shortest Path, and Vertex Cut and considered diverse parameters for kernelization, including the number of tokens k, the budget b, as well as structural parameters such as pathwidth.
The solution discovery framework itself, which is the space where the previously described solution discovery problems can be defined, effectively models several interesting real-world applications. However, despite its potential, this framework has seen limited research and was only recently formally introduced by Fellows et al. [ECAI 2023]. Through the talk, we will familiarize ourselves with some of the key developments under this framework.