, Open problem session of the Workshop on Kernelization (WorKer), 2013.
Crown structures for vertex cover kernelization. Theory of Computing Systems, vol.41, p.411430, 2007. ,
On problems without polynomial kernels, Journal of Computer and System Sciences, vol.75, issue.8, p.423434, 2009. ,
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
Kernelization lower bounds by crosscomposition, SIAM Journal on Discrete Mathematics, vol.28, issue.1, p.277305, 2014. ,
Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels, 2008. ,
The monadic second-order theory of graphs I: recognisable sets of nite graphs. Information and Computation, vol.85, p.663, 1990. ,
, Parameterized Algorithms, 2015.
On the hardness of losing width. Theory of Computing Systems, vol.54, p.7382, 2014. ,
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. ,
, Graph Theory. Graduate Texts in Mathematics, 2005.
Kernelization lower bounds through colors and ids, ACM Transactions on Algorithms, vol.11, issue.2, p.13, 2014. ,
, Ecient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions. Algorithmica, vol.58, issue.3, p.790810, 2010.
Fundamentals of parameterized complexity, 2013. ,
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. ,
Parameterized Complexity Theory. Texts in Theoretical Computer Science, 2006. ,
Bidimensionality and kernels, Proc. of the 21st ACM-SIAM Symp. on Disc. Algorithms (SODA), p.503510, 2010. ,
Vertex cover structural parameterization revisited, 2016. ,
, Note that our kernel for VC/c-tdmod is not covered by the meta-result of, vol.20
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 ,
Kernelization using structural parameters on sparse graph classes, Journal of Computer and System Sciences, vol.84, p.219242, 2017. ,
Meta-kernelization with structural parameters, Journal of Computer and System Sciences, vol.82, issue.2, p.333346, 2016. ,
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
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. ,
Parameter ecology for feedback vertex set, Tsinghua Science and Technology, vol.19, issue.4, p.387409, 2014. ,
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
Planar formulae and their uses, SIAM Journal on Computing, vol.11, issue.2, pp.329-343, 1982. ,
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. ,
, Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00768681
Invitation to Fixed-Parameter Algorithms, 2006. ,
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. ,
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. ,
A faster parameterized algorithm for treedepth, Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), vol.8572, p.931942, 2014. ,
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 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
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) ,