Structural parameters of graphs play a central role in modern graph theory and algorithm design. They provide a way to measure the structural complexity of graphs and often allow computationally hard problems to become tractable when the parameter is small.
Within the framework of parameterized complexity, many classical NP-hard problems admit efficient algorithms when restricted to graphs of bounded structural parameters.
In this thesis, we study block treedepth, a generalization of treedepth where vertex removal occurs at the blocks of the given graph, from both structural and algorithmic perspectives. First, we present an alternative definition of block treedepth that is inspired by the characterization of treedepth via weak coloring numbers. Instead of describing the parameter through vertex deletions, we reinterpret the process in terms of deleting sets of edges that correspond to the incident edges of vertices. These edge sets naturally form stars, which leads to a formulation based on star partitions of the edge set together with valid deletion orders of these stars. This viewpoint provides a clearer interpretation of the deletion process.
We also introduce and study a new graph parameter called vertex deletion to starforest. For a graph G, this parameter measures the minimum number of vertices whose removal transforms G into a forest whose connected components are stars. The parameter forms part of a broader family of parameters, vertex deletion to d-forest, where the remaining graph is required to be a forest of bounded depth d as well as a restriction of feedback vertex set. The star-forest case corresponds to the special case where the depth is at most two.
The main algorithmic contribution of this thesis concerns the parameterized complexity of the BLOCK TREEDEPTH decision problem. In particular, we investigate the problem when it is parameterized by the vertex deletion to star-forest number. Using a series of tailor-made reduction rules, we develop a kernelization algorithm that reduces any instance to an equivalent instance whose size is bounded polynomially by the parameter. As a consequence, the problem is fixed-parameter tractable with respect to this parameter.