Structural Parameterizations for Bounded Degree Vertex Deletion Revisited

In this talk we focus on the setting of structural parameterizations for graph problems, and in particular on how hypotheses of Fine-grained Complexity, namely SETH and ETH, can be used to obtain oftentimes tight lower bounds for parameterized algorithms. Towards this end, we will study the Bounded Degree Vertex Deletion problem, a natural generalization of Vertex Cover. We will present tight lower bounds under different parameterizations, exhibiting a variety of techniques that might be useful for other reductions as well.

This is a joint work with M. Lampis.