Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width

In this paper we investigate the parameterized complexity for NP-hard graph problems parameterized by a structural parameter modular-width. We develop a recipe that is able to simplify the process of obtaining polynomial Turing compressions for a class of graph problems parameterized by modular-width. By using the recipe, we demonstrate that several problems, which include Chromatic Number, Independent Det, Hamiltonian Cycle, etc. have polynomial Turing compressions parameterized by modular-width. In addition, under the assumption that P $\neq$ NP, we provide tight kernels for a few problems such as Steiner Tree parameterized by modular-width. As a byproduct of the result of the tight kernels, new parameterized algorithms for these problems are obtained.