, Open problem session of the Workshop on Kernelization (WorKer), 2013.

F. N. Abu-khzam, M. R. Fellows, M. A. Langston, and W. H. Suters, Crown structures for vertex cover kernelization. Theory of Computing Systems, vol.41, p.411430, 2007.

H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, p.423434, 2009.

H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh et al., Meta) Kernelization, Proc. of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), p.629638, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-01483628

H. L. Bodlaender, B. M. Jansen, and S. Kratsch, Kernelization lower bounds by crosscomposition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, p.277305, 2014.

H. L. Bodlaender, S. Thomassé, and A. Yeo, Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels, 2008.

B. Courcelle, The monadic second-order theory of graphs I: recognisable sets of nite graphs. Information and Computation, vol.85, p.663, 1990.

M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx et al., Parameterized Algorithms, 2015.

M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, On the hardness of losing width. Theory of Computing Systems, vol.54, p.7382, 2014.

M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. Van-rooij et al., Wojtaszczyk. Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time, Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), p.150159, 2011.

R. Diestel, Graph Theory. Graduate Texts in Mathematics, 2005.

M. Dom, D. Lokshtanov, and S. Saurabh, Kernelization lower bounds through colors and ids, ACM Transactions on Algorithms, vol.11, issue.2, p.13, 2014.

F. Dorn, E. Penninkx, H. L. Bodlaender, and F. V. Fomin, Ecient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions. Algorithmica, vol.58, issue.3, p.790810, 2010.

R. G. Downey and M. R. Fellows, Fundamentals of parameterized complexity, 2013.

E. Eiben, R. Ganian, and S. Szeider, Meta-kernelization using well-structured modulators, Proc. of the 10th International Symposium on Parameterized and Exact Computation (IPEC), volume 43 of LIPIcs, p.114126, 2015.

J. Flum and M. Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science, 2006.

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Bidimensionality and kernels, Proc. of the 21st ACM-SIAM Symp. on Disc. Algorithms (SODA), p.503510, 2010.

F. V. Fomin and T. J. Strømme, Vertex cover structural parameterization revisited, 2016.

, Note that our kernel for VC/c-tdmod is not covered by the meta-result of, vol.20

. V-|x|+1-=-v-(g)-\-x, The number of parts is polynomial in |X|, each satisfying the rankwidth condition: rw(V |X|+1 ) ? tw(V |X|+1 ) + 1 ? td(V |X|+1 ) + 1 ? c + 1. However

J. Gajarský, P. Hlinený, J. Obdrzálek, S. Ordyniak, F. Reidl et al., Kernelization using structural parameters on sparse graph classes, Journal of Computer and System Sciences, vol.84, p.219242, 2017.

R. Ganian, F. Slivovsky, and S. Szeider, Meta-kernelization with structural parameters, Journal of Computer and System Sciences, vol.82, issue.2, p.333346, 2016.

V. Garnero, C. Paul, I. Sau, and D. M. Thilikos, Explicit linear kernels via dynamic programming, SIAM Journal on Discrete Mathematics, vol.29, issue.4, p.18641894, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01084007

B. Jansen and H. Bodlaender, Vertex cover kernelization revisited: Upper and lower bounds for a rened parameter, Proc. of the 28th Symposium on Theoretical Aspects of Computer Science (STACS), vol.9, p.177188, 2011.

B. M. Jansen, V. Raman, and M. Vatshelle, Parameter ecology for feedback vertex set, Tsinghua Science and Technology, vol.19, issue.4, p.387409, 2014.

E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith et al., Linear kernels and single-exponential algorithms via protrusion decompositions, ACM Transactions on Algorithms, vol.12, issue.2, p.21, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-01288472

D. Lichtenstein, Planar formulae and their uses, SIAM Journal on Computing, vol.11, issue.2, pp.329-343, 1982.

D. Majumdar, V. Raman, and S. Saurabh, Kernels for structural parameterizations of vertex cover -case of small degree modulators, Proc. of the 10th International Symposium on Parameterized and Exact Computation (IPEC), volume 43 of LIPIcs, p.331342, 2015.

J. Nesetril, P. , and O. Mendez, Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00768681

R. Niedermeier, Invitation to Fixed-Parameter Algorithms, 2006.

R. Niedermeier, Reections on multivariate algorithmics and problem parameterization, Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 5 of LIPIcs, p.1732, 2010.

G. Philip, V. Raman, and S. Sikdar, Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels, Proc. of the 17th Annual European Symposium on Algorithms (ESA), vol.5757, p.694705, 2009.

F. Reidl, P. Rossmanith, F. S. Villaamil, and S. Sikdar, A faster parameterized algorithm for treedepth, Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), vol.8572, p.931942, 2014.

J. Rué, I. Sau, and D. M. Thilikos, A List of problems considered in this article Independent Set (IS) Instance: (G, k) with G = (V, E) grph nd k n integerF Question: heide whether ?(G) ? kD iFeFD if ?S ? V suh tht ?e ? E, e S nd |S| ? kF c-treedepth modulator Independent Set (c-tdmod-IS) Instance, ACM Transactions on Algorithms, vol.10, issue.2, 2014.

, Annotated c-treedepth modulator Independent Set @EcEtdmodEISA Instance

?. , E. , H. Hypergrph-strutured-s-followsx-v-=-x-rd-e-=-e-x,r-e-r, and R. Is, E A,B hve one endpoint in A nd the other in BD nd H ? 2 X is set of hyperedges where eh H ? H is entirely ontined in XF

. ?-x-is-cetreedepth-modultor-@s-g-;-s-?-v-suh-tht-?e-?-e,-e-?-s-=-?-nd-|s|-?-kf-;-s-?-v-suh-tht-?u-?-v-\-s,-?v-?-s-|-{u and . Kf, Instance: (G, k) with G = (V, E) grph nd k n integerF Question: heide whether G hs feedk vertex set of size t most kD iFeFD if there exists S ? V suh tht G[V \ S] is forest nd |S| ? k Dominating Set (DS) Instance: (G, k) with G = (V, E) grph nd k n integerF Question: heide whether G hs dominting set of size t most kD iFeFD if there exists, is not hypergrphD its treedepth is orretly de(ned nd we hve td(V \ X) ? cAF ? k is positive integerF Question: heide whether ?(G)