Abstract: This project studies vertex deletion problems, a central topic in graph algorithms and parameterized complexity. These problems ask whether a small set of vertices can be removed from a graph so that the remaining graph has a desired structure, such as being a forest, bipartite graph, chordal graph, interval graph, or permutation graph. While several important cases are well understood, many natural graph classes still have unknown parameterized complexity and kernelization status.

The project aims to advance the theory of vertex deletion by studying deletion to important target graph classes, especially those not covered by existing general frameworks. It will also investigate related secluded subgraph problems, where the goal is to find a large structured subgraph that has limited interaction with the rest of the graph. By exploring both undirected and directed settings, the project seeks to develop new fixed-parameter algorithms, kernelization results, and complexity classifications for graph problems that remain largely unexplored.