How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs? - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Algorithmica Année : 2019

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

Marin Bougeret
Ignasi Sau

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.[...]
Fichier principal
Vignette du fichier
How.pdf (695.5 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-02410618 , version 1 (13-12-2019)

Identifiants

Citer

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

Altmetric

Partager

More