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
Journal Articles Algorithmica Year : 2019

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

Marin Bougeret
Ignasi Sau

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

Dates and versions

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

Identifiers

Cite

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⟩
105 View
73 Download

Altmetric

Share

More