Skip to Main content Skip to Navigation
Journal articles

How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?

Marin Bougeret 1 Ignasi Sau Valls 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.[...]
Document type :
Journal articles
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02410618
Contributor : Ignasi Sau <>
Submitted on : Friday, December 13, 2019 - 10:05:56 PM
Last modification on : Thursday, June 11, 2020 - 8:56:04 PM

File

Identifiers

Collections

Citation

Marin Bougeret, Ignasi Sau Valls. How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?. Algorithmica, Springer Verlag, 2019, 81 (10), pp.4043-4068. ⟨10.1007/s00453-018-0468-8⟩. ⟨lirmm-02410618⟩

Share

Metrics

Record views

66

Files downloads

84