How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?
Résumé
In the last years, kernelization with structural parameters has been an active area of research within the eld of parameterized complexity. As a relevant example, Gajarský et al. [ESA 2013] proved that every graph problem satisfying a property called nite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c, where c ≥ 1 is a xed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to nd problems that, while admitting polynomial kernels on sparse graphs, behave dierently on general graphs.[...]
Loading...