Preprocessing Complexity for Some Graph Problems Parameterized by Structural Parameters

06/22/2023
by   Manuel Lafond, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset