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
In the recently introduced class of solution discovery problems [Fellows et al., ECAI 2023], we are given an initial infeasible solution for an instance under a source problem Π and tasked with transforming it into a feasible solution (under Π) via a bounded number b of modification steps. While the paper of Fellows et al., have mainly focused on fundamental NP-hard graph source problems such as Dominating Set and Coloring, my joint work with Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand and Sebastian Siebertz explores solution discovery problems of graph vertex (or edge) subset source problems in P, namely Spanning Tree, Shortest Path, Matching, and Vertex/Edge Cut. When the modification step consists of changing the current infeasible solution by removing a vertex (resp. edge) from the infeasible set and replacing it with an adjacent vertex (resp. edge), we show that almost all considered problems become NP-complete. This motivates the study of these problems under parameterized complexity assumptions. Under these assumptions, our work considered the size of the (infeasible or feasible) solutions and the bound on the number of modification steps (b) as parameters.
Solution discovery problems are particularly compelling due to their utility in dynamic real-life environments, where systems must adapt to changing circumstances. Through the talk, we will discuss the results of my joint work, familiarize ourselves with related works and see how solution discovery algorithms are different than other algorithms considered in the literature before.