integer $\ell {\geqslant}1$, one aims at finding either minor-models that are pairwise at distance at least $\ell$ in $G$ (<span style="font-variant:small-caps;">$\ell$-${\mathcal}{F}$-Packing</span>), or such that each vertex in $G$ belongs to at most $\ell$ minors-models (<span style="font-variant:small-caps;">${\mathcal}{F}$-Packing with $\ell$-Membership</span>). Finally, we also provide linear kernels for the versions of these problems where one wants to pack [*subgraphs*]{} instead of minors.'
author:
- 'Valentin Garnero[^1]'
- 'Christophe Paul$^{\dagger}$'
- 'Ignasi Sau$^{\dagger}$'
- 'Dimitrios M. Thilikos$^{\dagger}$[^2]'
bibliography:
- 'linearkernels.bib'
title: 'Explicit linear kernels for packing problems[^3]'
---

**Keywords:** Parameterized complexity; linear kernels; packing problems; dynamic programming; protrusion replacement; graph minors.

Introduction {#sec:intro}
============

**Motivation.** A fundamental notion in parameterized complexity (see [@CyganFKLMPPS15] for a recent textbook) is that of *kernelization*, which asks for the existence of polynomial-time preprocessing algorithms producing equivalent instances whose size depends exclusively on the parameter $k$. Finding kernels of size polynomial or linear in $k$ (called *linear kernels*) is one of the major goals of this area. A pioneering work in this direction was the linear kernel of Alber *et al*. [@AFN04] for <span style="font-variant:small-caps;">Dominating Set</span> on planar graphs, generalized by Guo and Niedermeier [@GuNi07] to a family of problems on planar graphs. Several algorithmic meta-theorems on kernelization have 