How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?

Marin Bougeret 1 Ignasi Sau 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 field of parameterized complexity. As a relevant example, Gajarsk{\`y} \emph{et al}.~[ESA 2013] proved that every graph problem satisfying a property called finite 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$ for a fixed integer $c \geq 1$. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that \textsc{Vertex Cover} admits a polynomial kernel on general graphs for any integer $c \geq 1$, and that \textsc{Dominating Set} does {\sl not} for any integer $c \geq 2$ even on degenerate graphs, unless $\text{NP} \subseteq \text{coNP}/\text{poly}$. For the positive result, we build on the techniques of Jansen and Bodlaender~[STACS 2011], and for the negative result we use a polynomial parameter transformation for $c\geq 3$ and an \textsc{or}-cross-composition for $c = 2$. As existing results imply that \textsc{Dominating Set} admits a polynomial kernel on degenerate graphs for $c = 1$, our result provides a dichotomy about the existence of polynomial problems for \textsc{Dominating Set} on degenerate graphs with this parameter.
Type de document :
Communication dans un congrès
IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.10:1--10:13, 2018, 〈https://algo2017.ac.tuwien.ac.at/ipec/〉. 〈10.4230/LIPIcs.IPEC.2017.10〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01730228
Contributeur : Marin Bougeret <>
Soumis le : mardi 13 mars 2018 - 10:18:09
Dernière modification le : jeudi 15 novembre 2018 - 18:26:37
Document(s) archivé(s) le : jeudi 14 juin 2018 - 17:43:37

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Marin Bougeret, Ignasi Sau. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?. IPEC: International symposium on Parameterized and Exact Computation, Sep 2017, Vienne, Austria. 12th International Symposium on Parameterized and Exact Computation, LIPIcs (89), pp.10:1--10:13, 2018, 〈https://algo2017.ac.tuwien.ac.at/ipec/〉. 〈10.4230/LIPIcs.IPEC.2017.10〉. 〈lirmm-01730228〉

Partager

Métriques

Consultations de la notice

170

Téléchargements de fichiers

49