  Structural graph parameters play an important role in parameterized
complexity, including in kernelization. Notably, vertex cover, neighborhood
diversity, twin-cover, and modular-width have been studied extensively in the
last few years. However, there are many fundamental problems whose
preprocessing complexity is not fully understood under these parameters.
Indeed, the existence of polynomial kernels or polynomial Turing kernels for
famous problems such as Clique, Chromatic Number, and Steiner Tree has only
been established for a subset of structural parameters. In this work, we use
several techniques to obtain a complete preprocessing complexity landscape for
over a dozen of fundamental algorithmic problems.
