---
abstract: 'During the last years, several algorithmic meta-theorems have appeared (Bodlaender *et al*. \[FOCS 2009\], Fomin *et al*. \[SODA 2010\], Kim *et al*. \[ICALP 2013\]) guaranteeing the [*existence*]{} of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them [*constructive*]{} kernels with reasonably low [*explicit*]{} constants. To fill this gap, we recently presented \[STACS 2014\] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of [*vertices*]{}. In this article we enhance our framework to deal with [*packing*]{} problems, that is, problems whose solutions can be certified by collections of [*subgraphs*]{} of the input graph satisfying certain properties. ${\mathcal F}$-<span style="font-variant:small-caps;">Packing</span> is a typical example: for a family ${\mathcal F}$ of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph $G$ contains $k$ vertex-disjoint subgraphs such that each of them contains a graph in ${\mathcal F}$ as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of ${\mathcal F}$-<span style="font-variant:small-caps;">Packing</span>: for an 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 appeared in the last years, starting with the result of Bodlaender *et al*. [@BFL+09] on graphs of bounded genus. It was followed-up by similar results on larger sparse graph classes, such as graphs excluding a minor [@FLST10] or a topological minor [@KLP+12].

The above results guarantee the [*existence*]{} of linear kernels on sparse graph classes for problems satisfying some generic conditions, but it is hard to derive from them [*constructive*]{} kernels with [*explicit*]{} constants. We recently made in [@KviaDP] a significant step toward a fully constructive meta-kernelization theory on sparse graphs with explicit constants. In a nutshell, the main idea is to substitute the algorithmic power of CMSO logic that was used in [@BFL+09; @FLST10; @KLP+12] with that of dynamic programming (DP for short) on graphs of bounded decomposability (i.e., bounded treewidth). We refer the reader to the introduction of [@KviaDP] for more details. Our approach provides a DP framework able to construct linear kernels for families of problems on sparse graphs whose solutions can be certified by a subset of [*vertices*]{} of the input graph, such as $r$-<span style="font-variant:small-caps;">Dominating Set</span> or <span style="font-variant:small-caps;">Planar-$\mathcal{F}$-Deletion</span>.

**Our contribution.** In this article we make one more step in the direction of a fully constructive meta-kernelization theory on sparse graphs, by enhancing the existing framework [@KviaDP] in order to deal with [*packing*]{} problems. These are problems whose solutions can be certified by collections of [*subgraphs*]{} of the input graph satisfying certain properties. We call these problems *packing-certifiable*, as opposed to *vertex-certifiable* ones. For instance, deciding whether a graph $G$ contains at least $k$ vertex-disjoint cycles is a typical packing-certifiable problem. This problem, called <span style="font-variant:small-caps;">Cycle Packing</span>, is [[FPT]{}]{} as it is minor-closed, but it is unlikely to admit polynomial kernels on general graphs [@BodlaenderTY11].

As an illustrative example, for a family of connected graphs ${\mathcal F}$ containing at least one planar graph, we provide a linear kernel on sparse graphs for the <span style="font-variant:small-caps;">${\mathcal F}$-Packing</span> problem[^4]: decide whether a graph $G$ contains at least $k$ vertex-disjoint subgraphs such that each of them contains a graph in ${\mathcal F}$ as a minor, parameterized by $k$. We provide linear kernels as well for the following two [*orthogonal generalizations*]{} of ${\mathcal F}$-<span style="font-variant:small-caps;">Packing</span>: for an 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>). While only the [*existence*]{} of linear kernels for <span style="font-variant:small-caps;">${\mathcal F}$-Packing</span> was known [@BFL+09], to the best of our knowledge no kernels were known for <span style="font-variant:small-caps;">$\ell$-${\mathcal}{F}$-Packing</span> and <span style="font-variant:small-caps;">${\mathcal}{F}$-Packing with $\ell$-Membership</span>, except for <span style="font-variant:small-caps;">$\ell$-${\mathcal}{F}$-Packing</span> when $\mathcal{F}$ consists only of a triangle and the maximum degree is also considered as a parameter [@AtminasKR14]. We would like to note that the kernels for <span style="font-variant:small-caps;">${\mathcal F}$-Packing</span> and for <span style="font-variant:small-caps;">${\mathcal}{F}$-Packing with $\ell$-Membership</span> apply to minor-free graphs, while those for <span style="font-variant:small-caps;">$\ell$-${\mathcal}{F}$-Packing</span> for $\ell {\geqslant}2$ apply to the smaller class of apex-minor-free graphs. We also provide linear kernels for the versions of the above problems where one wants to pack [*subgraphs*]{} instead of minors (as one could expect, the kernels for subgraphs are considerably simpler than those for minors). We call the respective problems <span style="font-variant:small-caps;">$\ell$-${\cal F}$-Subgraph-Packing</span> and <span style="font-variant:small-caps;">${\mathcal}{F}$-Subgraph-Packing with $\ell$-Membership</span>. While the first problem can be seen as a broad generalization of $\ell$-<span style="font-variant:small-caps;">Scattered Set</span> (see for instance [@BFL+09; @KviaDP]), the second one was recently defined by Fernau *et al*. [@FernauLR15], motivated by the problem of discovering overlapping communities (see also [@RomeroL14-WALCOM; @RomeroL14-CSR] for related problems about detecting overlapping communities): the parameter $\ell$ bounds the number of communities that a member of a network can belong to. More precisely, the goal is to find in a graph $G$ at least $k$ subgraphs isomorphic to a member of $\mathcal{F}$ such that every vertex in $V(G)$ belongs to at most $\ell$ subgraphs. This type of overlap was also studied by Fellows *et al*. [@FellowsGKNU11] in the context of graph editing. Fernau *et al*. [@FernauLR15] proved, in particular, that the <span style="font-variant:small-caps;">$\mathcal{F}$-Subgraph-Packing with $\ell$-Membership</span> problem is -hard for all values of $\ell {\geqslant}1$ when ${\mathcal F}= \{F\}$ and $F$ is an arbitrary connected graph with at least three vertices, but polynomial-time solvable for smaller graphs. Note that <span style="font-variant:small-caps;">$\mathcal{F}$-Subgraph-Packing with $\ell$-Membership</span> generalizes the <span style="font-variant:small-caps;">$\mathcal{F}$-Subgraph-Packing</span> problem, which consists in finding in a graph $G$ at least $k$ vertex-disjoint subgraphs isomorphic to a member of $\mathcal{F}$. The smallest kernel for the <span style="font-variant:small-caps;">$\mathcal{F}$-Subgraph-Packing</span> problem [@Moser09] has size $O(k^{r-1})$, where $\mathcal{F} = \{F\}$ and $F$ is an arbitrary graph on $r$ vertices. A list of references of kernels for particular cases of the family $\mathcal{F}$ can be found in [@FernauLR15]. Concerning the kernelization of <span style="font-variant:small-caps;">$\mathcal{F}$-Subgraph-Packing with $\ell$-Membership</span>, Fernau *et al*. [@FernauLR15] provided a kernel on general graphs with $O((r+1)^r k^r)$ vertices, where $r$ is the maximum number of vertices of a graph in $\mathcal{F}$. In this article we improve this result on graphs excluding a fixed graph as a minor, by providing a linear kernel for <span style="font-variant:small-caps;">$\mathcal{F}$-Subgraph-Packing with $\ell$-Membership</span> when $\mathcal{F}$ is any family of (not necessarily planar) connected graphs.

**Our techniques: vertex-certifiable vs. packing-certifiable problems**. It appears that packing-certifiable problems are intrinsically more involved than vertex-certifiable ones. This fact is well-known when speaking about [[FPT]{}]{}-algorithms on graphs of bounded treewidth [@CyganNPPRW11; @LokshtanovMS11], but we need to be more precise with what we mean by being “more involved” in our setting of obtaining kernels via DP on a tree decomposition of the input graph. Loosely speaking, the framework that we presented in [@KviaDP] and that we need to redefine and extend here, can be summarized as follows. First of all, we propose a general definition of a problem *encoding* for the tables of DP when solving parameterized problems on graphs of bounded treewidth. Under this setting, we provide three general conditions guaranteeing that such an encoding can yield a so-called *protrusion replacer*, which in short is a procedure that replaces large “protrusions” (i.e., subgraphs with small treewidth and small boundary) with “equivalent” subgraphs of constant size. Let us be more concrete on these three conditions that such an encoding ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ needs to satisfy in order to obtain an explicit linear kernel for a parameterized problem $\Pi$. The first natural condition is that on a graph $G$ without boundary, the optimal size of the objects satisfying the constraints imposed by ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ coincides with the optimal size of solutions of $\Pi$ in $G$; in that case we say that ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ is a *$\Pi$-encoder*. On the other hand, we need that when performing DP using the encoding ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$, we can use tables such that the maximum difference among all the values that need to be stored is bounded by a function $g$ of the treewidth; in that case we say that ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ is *$g$-confined*. Finally, the third condition requires that ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ is “suitable” for performing DP, in the sense that the tables at a given node of a tree decomposition can be computed using only the information stored in the tables of its children (as it is the case of practically all natural DP algorithms); in that case we say that ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ is *DP-friendly*. These two latter properties exhibit some fundamental differences when dealing with vertex-certifiable or packing-certifiable problems.

Indeed, as discussed in more detail in Section \[sec:generic\], with an encoding ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ we associate a function $f^{{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ that corresponds, roughly speaking, to the maximum size of a partial solution that satisfies the constraints defined by ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$. In order for an encoder to be $g$-confined for some function $g(t)$ of the treewidth $t$, for some vertex-certifiable problems such as $r$-<span style="font-variant:small-caps;">Scattered Set</span> (see [@KviaDP]) we need to “force” the confinement artificially, in the sense that we directly discard the entries in the tables whose associated values differ by more than $g(t)$ from the maximum (or minimum) ones. Fortunately, we can prove that an encoder with this modified function is still DP-friendly. However, this is not the case for packing-certifiable problems such as <span style="font-variant:small-caps;">$\mathcal{F}$-Packing</span>. Intuitively, the difference lies on the fact that in a packing-certifiable problem, a solution of size $k$ can contain arbitrarily many vertices (for instance, if one wants to find $k$ disjoint cycles in an $n$-vertex graph with girth $\Omega(\log n)$) and so it can as well contain arbitrarily many vertices from any subgraph corresponding to a rooted subtree of a tree decomposition of the input graph $G$. This possibility prevents us from being able to prove that an encoder is DP-friendly while still being $g$-confined for some function $g$, as in order to fill in the entries of the tables at a given node, one may need to retrieve information from the tables of other nodes different from its children. To circumvent this problem, we introduce another criterion to discard the entries in the tables of an encoder: we recursively discard the entries of the tables whose associated partial solutions [*induce*]{} partial solutions at some lower node of the rooted tree decomposition that need to be discarded. That is, if an entry of the table needs to be discarded at some node of a tree decomposition, we [*propagate*]{} this information to all the other nodes.

**Organization of the paper.** Some basic preliminaries can be found in Section \[sec:prelim\], including graph minors, parameterized problems, (rooted) tree decompositions, boundaried graphs, the canonical equivalence relation $\equiv_{\Pi,t}$ for a problem $\Pi$ and an integer $t$, FII, protrusions, and protrusion decompositions. The reader not familiar with the background used in previous work on this topic may see [@BFL+09; @FLST10; @KLP+12; @KviaDP]. In Section \[sec:generic\] we introduce the basic definitions of our framework and present an explicit protrusion replacer for packing-certifiable problems. Since many definitions and proofs in this section are quite similar to the ones we presented in [@KviaDP], for better readability we moved the proofs of the results marked with ‘$[\star]$’ to Appendix \[ap:framework\]. Before moving to the details of each particular problem, in Section \[sec:applications\] we summarize the main ingredients that we use in our applications. The next sections are devoted to showing how to apply our methodology to various families of problems. More precisely, we start in Section \[sec: FPack\] with the linear kernel for <span style="font-variant:small-caps;">Connected-Planar-${\mathcal}{F}$-Packing</span>. This problem is illustrative, as it contains most of the technical ingredients of our approach, and will be generalized later in the two orthogonal directions mentioned above. Namely, in Section \[sec: rFPack\] we deal with the variant in which the minor-models are pairwise at distance at least $\ell$, and in Section \[sec: FMemb\] with the version in which each vertex can belong to at most $\ell$ minor-models. In Section \[sec: FSub\] we adapt the machinery developed for packing minors to packing subgraphs, considering both variants of the problem. For the sake of completeness, each of the considered problems will be redefined in the corresponding section. Finally, Section \[sec:conclusions\] concludes the article.

Preliminaries {#sec:prelim}
=============

In our article graphs are undirected, simple, and without loops. We use standard graph-theoretic notation; see for instance [@Die05]. We denote by $d_G(v,w)$ the distance in $G$ between two vertices $v$ and $w$ and by $d_G(W_1,W_2) = \min\{ d_G(w_1,w_2) : w_1\in W_1, w_2\in W_2 \}$ the distance between two sets of vertices $W_1$ and $W_2$ of $G$. Given $S \subseteq V(G)$, we denote by $N(S)$ the set of vertices in $V(G) \setminus S$ having at least one neighbor in $S$.

A parameterized graph problem ${\Pi}$ is called *packing-certifiable* if there exists a language $L^{\Pi}$ (called [*certifying language for $\Pi$*]{}) defined on pairs $(G,{\cal S})$, where $G$ is a graph and ${\cal S}$ is a collection of subgraphs of $G$, such that $(G,k)$ is a [<span style="font-variant:small-caps;">Yes</span>]{}-instance of $\Pi$ if and only if there exists a collection ${\cal S}$ of subgraphs of $G$ with $|{\cal S}| {\geqslant}k$ such that $(G,{\cal S}) \in L^{\Pi}$.

In the above definition, for the sake of generality we do not require the subgraphs in the collection ${\cal S}$ to be pairwise distinct. Also, note that the subclass of packing-certifiable problems where each subgraph in ${\cal S}$ is restricted to consist of a single vertex corresponds to the class of vertex-certifiable problems defined in [@KviaDP].

For a class of graphs [${\mathcal}{G}$]{}, we denote by $\Pi_{\ensuremath{{\mathcal}{G}}\xspace}$ the problem $\Pi$ where the instances are restricted to contain graphs belonging to [${\mathcal}{G}$]{}. With a packing-certifiable problem we can associate in a natural way an optimization function as follows.

\[defi:optimization-function\] Given a packing-certifiable parameterized problem $\Pi$, the *maximization function* $f^{\Pi}: \Gamma^* \rightarrow \mathbb{N}\cup\{-\infty\}$ is defined as $$\begin{aligned}
f^{\Pi}(G)=\
\left\{\begin{array}{lll}
  & \max\{|{\cal S}| : (G,{\cal S}) \in L^{\Pi}\} & \mbox{, if there exists such an ${\cal S}$ and}\\
  & - \infty                     & \mbox{, otherwise}.
\end{array}\right.\end{aligned}$$

\[defi:boundaried\] A *boundaried graph* is a graph $G$ with a set $B \subseteq V (G)$ of distinguished vertices and an injective labeling $\lambda_G: B \to \mathbb{N}$. The set $B$ is called the *boundary* of $G$ and it is denoted by $\partial(G)$. The set of labels is denoted by $\Lambda(G) = \{\lambda_G(v) : v \in \partial(G) \}$. We say that a boundaried graph is a *$t$-boundaried graph* if $\Lambda(G) \subseteq \{1, \ldots ,t\}$.

We denote by [${\mathcal}{B}_t$]{}the set of all $t$-boundaried graphs.

\[defi:gluing\] Let $G_1$ and $G_2$ be two boundaried graphs. We denote by $G_1 \oplus G_2$ the graph obtained from $G$ by taking the disjoint union of $G_1$ and $G_2$ and identifying vertices with the same label in the boundaries of $G_1$ and $G_2$. In $G_1 \oplus G_2$ there is an edge between two labeled vertices if there is an edge between them in $G_1$ or in $G_2$.

Given $G = G_1 \oplus G_2$ and $G_2'$, we say that $G' = G_1 \oplus G_2'$ is the graph obtained from $G$ by *replacing* $G_2$ with $G_2'$. The following notion was introduced by Bodlaender *el al*. [@BFL+09].

\[defi:cano\] Let $\Pi$ be a parameterized problem and let $t \in \mathbb{N}$. Given $G_1,G_2 \in {\ensuremath{{\mathcal}{B}_t}\xspace}$, we say that $G_1 \equiv_{\Pi} G_2$ if $\Lambda(G_1) = \Lambda(G_2)$ and there exists a transposition constant ${\ensuremath{\Delta_{\Pi,t}}\xspace}(G_1,G_2) \in \mathbb{Z}$ such that for every $H \in {\ensuremath{{\mathcal}{B}_t}\xspace}$ and every $k \in \mathbb{Z}$, it holds that $(G_1 \oplus H, k) \in \Pi$ if and only if $(G_2 \oplus H, k+{\ensuremath{\Delta_{\Pi,t}}\xspace}(G_1,G_2)) \in \Pi$.

A *tree decomposition* of a graph $G$ is a couple $(T,{\mathcal}{X} = \{ B_x : x \in V(T) \})$, where $T$ is a tree and such that $\bigcup_{x \in V(T)} B_x = V(G)$, for every edge $\{u,v\} \in E (G)$ there exists $x \in V(T)$ such that $u,v \in B_x$, and for every vertex $u \in V(G)$ the set of nodes $\{ x\in V(T) : u \in B_x \}$ induce a subtree of $T$. The vertices of $T$ are referred to as *nodes* and the sets $B_x$ are called bags.

A *rooted tree decomposition* $(T,{\mathcal}{X},r)$ is a tree decomposition with a distinguished node $r$ selected as the *root*. A *nice tree decomposition* $(T,{\mathcal}{X},r)$ (see [@Klo94]) is a rooted tree decomposition where $T$ is binary and for each node $x$ with two children $y,z$ it holds $B_x =B_y =B_z$ and for each node $x$ with one child $y$ it holds $B_x =B_y \cup \{u\}$ or $B_x =B_y \setminus \{ u\}$ for some $u \in V(G)$. The *width* of a tree decomposition is the size of a largest bag minus one. The *treewidth* of a graph, denoted by ${{\mathbf{tw}}}(G)$, is the smallest width of a tree decomposition of $G$. A *treewidth-modulator* of a graph $G$ is a set $X \subseteq V(G)$ such that ${{\mathbf{tw}}}(G-X) {\leqslant}t$, for some fixed constant $t$.

Given a bag $B$ (resp. a node $x$) of a rooted tree decomposition $T$, we denote by $G_B$ (resp. $G_x$), the subgraph induced by the vertices appearing in the subtree of $T$ rooted at the node corresponding to $B$ (resp. the node $x$). We denote by [${\mathcal}{F}_t$]{}the set of all $t$-boundaried graphs that have a rooted tree decomposition of width $t-1$ with all boundary vertices contained in the root-bag. Obviously ${\ensuremath{{\mathcal}{F}_t}\xspace}\subseteq {\ensuremath{{\mathcal}{B}_t}\xspace}$. (Note that graphs can be viewed as 0-boundaried graphs, hence we use a same alphabet $\Gamma$ for describing graphs and boundaried graphs.)

\[defi:prot\] Let $t,\alpha$ be positive integers. A *$t$-protrusion* $Y$ of a graph $G$ is an induced subgraph of $G$ with $|\partial(Y)| {\leqslant}t$ and $ {{\mathbf{tw}}}(Y) {\leqslant}t-1$, where $\partial(Y)$ is the set of vertices of $Y$ having neighbors in $V(G) \setminus V(Y)$. An *$(\alpha,t)$-protrusion decomposition* of a graph $G$ is a partition ${\cal P}=Y_{0}\uplus Y_{1}\uplus \cdots \uplus Y_{\ell}$ of $V(G)$ such that for every $1\leqslant i\leqslant \ell$, $N(Y_{i})\subseteq Y_{0}$, $\max\{\ell, |Y_{0}|\}\leqslant \alpha$, and for every $1\leqslant i\leqslant \ell$, $Y_i\cup N(Y_i)$ is a $t$-protrusion of $G$. When $(G,k)$ is the input of a parameterized problem with parameter $k$, we say that an $(\alpha,t)$-protrusion decomposition of $G$ is *linear* whenever $\alpha =O(k)$.

We say that a rooted tree decomposition of a protrusion $G$ (resp. a boundaried graph $G$) is *boundaried* if the boundary $\partial(G)$ is contained in the root bag. In the following we always consider boundaried nice tree decompositions of width $t-1$, which can be computed in polynomial time for fixed $t$ [@Klo94; @Bod96].

A framework to replace protrusions for packing problems {#sec:generic}
=======================================================

In this section we restate and in many cases modify the definitions given in [@KviaDP] in order to deal with packing-certifiable problems; we will point out the differences. As announced in the introduction, missing proofs can be found in Appendix \[ap:framework\].

**Encoders.** In the following we extend the definition of an encoder given in [@KviaDP Definition 3.2] so that it is able to deal with packing-certifiable problems. The main difference is that now the function ${\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}$ is incorporated in the definition of an encoder, since as discussed in the introduction we need to consider an additional scenario where the entries of the table are discarded (technically, this is modeled by setting those entries to “$-\infty$”) and for this we will have to deal with the partial solutions particular to each problem. In the applications of the next sections, we will call such functions that propagate the entries to be discarded *relevant*. We also need to add a condition about the [*computability*]{} of the function [$f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}$]{}, so that encoders can indeed be used for performing dynamic programming.

\[defi:encod\] An *encoder* is a triple ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}= ({\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace},{\ensuremath{L^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace},{\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace})$ where

-   is a function in $2^\mathbb{N} \to 2^{\Upsilon^*}$ that maps a finite subset of integers $ I \subseteq \mathbb{N}$ to a set ${\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)$ of strings over some alphabet $\Upsilon$. Each string $R \in {\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)$ is called an *encoding*. The *size* of the encoder is the function $s_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}} : \mathbb{N} \to \mathbb{N}$ defined as $s_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}(t)  :=  \max \{|{\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)| : I \subseteq \{1,\ldots,t\}\} $, where $|{\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)|$ denotes the number of encodings in ${\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)$;

-   is a computable language which accepts triples $(G,{\cal S},R)\in \Gamma^* \times \Sigma^* \times \Upsilon^*$, where $G$ is a boundaried graph, ${\cal S}$ is a collection of subgraphs of $G$ and $R \in {\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(\Lambda(G))$ is an encoding. If $(G,{\cal S},R)\in {\ensuremath{L^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}$, we say that ${\cal S}$ *satisfies* the encoding $R$ in $G$; and

-   is a computable function in $\Gamma^* \times \Upsilon^* \to \mathbb{N}\cup\{ -\infty\}$ that maps a boundaried graph $G$ and an encoding $R\in {\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(\Lambda(G))$ to an integer or to $-\infty$.

As it will become clear with the applications described in the next sections, an encoder is a formalization of the tables used by an algorithm that solves a packing-certifiable problem $\Pi$ by doing DP over a tree decomposition of the input graph. The encodings in ${\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)$ correspond to the entries of the DP-tables of graphs with boundary labeled by the set of integers $I$. The language Łidentifies certificates which are partial solutions satisfying the boundary conditions imposed by an encoding.

The following definition differs from [@KviaDP Definition 3.3] as now the function [$f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}$]{}is incorporated in the definition of an encoder [[${\mathcal}{E}_{}$]{}]{}.

\[defi:pi-encod\] Let $\Pi$ be a packing-certifiable problem. An encoder [[${\mathcal}{E}_{}$]{}]{}is a *$\Pi$-encoder* if ${\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(\emptyset)$ is a singleton, denoted by $\{R_\emptyset\}$, such that for any $0$-boundaried graph $G$, ${\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R_\emptyset) = f^\Pi(G)$.

The following definition allows to control the number of possible distinct values assigned to encodings and plays a similar role to FII or *monotonicity* in previous work [@BFL+09; @KLP+12; @FLST10].

\[def:confined\] An encoder ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ is *$g$-confined* if there exists a function $g : \mathbb{N} \to \mathbb{N}$ such that for any $t$-boundaried graph $G$ with $\Lambda(G) = I$ it holds that either $\{R \in {\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I) : {\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R) \neq - \infty \}= \emptyset\ $ or $\ \max_{R} \{{\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R)\neq - \infty \}\  -\   \min_{R} \{{\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R) \neq - \infty\}  \  {\leqslant}\ g(t)$.

For an encoder [[${\mathcal}{E}_{}$]{}]{}and a function $g$, in the next sections we will denote the [*relevant*]{} functions discussed before by ${\ensuremath{\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}}\xspace}$ to distinguish them from other functions that we will need.

**Equivalence relations and representatives.** We now define some equivalence relations on $t$-boundaried graphs.

\[defi:equiv\] Let [[${\mathcal}{E}_{}$]{}]{}be an encoder, let $G_1,G_2 \in {\ensuremath{{\mathcal}{B}_t}\xspace}$, and let ${\ensuremath{{\mathcal}{G}}\xspace}$ be a class of graphs.

1.  $G_1 {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}^*}\xspace} G_2$ if $\Lambda(G_1)=\Lambda(G_2)=: I$ and there exists an integer ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}(G_1,G_2)$ (depending on $G_1, G_2$) such that for any encoding $R   \in {\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(I)$ we have ${\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G_1,R) = {\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G_2,R) - {\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace} (G_1,G_2)$.

2.  $G_1 {\ensuremath{\sim_{{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace} G_2$ if either $G_1 \notin {\ensuremath{{\mathcal}{G}}\xspace}$ and $G_2 \notin {\ensuremath{{\mathcal}{G}}\xspace}$, or $G_1,G_2 \in {\ensuremath{{\mathcal}{G}}\xspace}$ and, for any $H \in {\ensuremath{{\mathcal}{B}_t}\xspace}$, $H \oplus G_1 \in {\ensuremath{{\mathcal}{G}}\xspace}$ if and only if $H \oplus G_2 \in {\ensuremath{{\mathcal}{G}}\xspace}$.

3.  $G_1 {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace}^*}\xspace} G_2$ if $G_1 {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}^*}\xspace} G_2$ and $G_1 {\ensuremath{\sim_{{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace} G_2$.

4.  If we restrict the graphs $G_1 , G_2$ to be in [${\mathcal}{F}_t$]{}, then the corresponding equivalence relations, which are a restriction of [[${\mathcal}{E}_{}$]{}]{}and [[${\mathcal}{E}_{}$]{}]{}, are denoted by [[${\mathcal}{E}_{}$]{}]{}and [[${\mathcal}{E}_{}$]{}]{}, respectively.

If for all encodings $R$, ${\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G_1,R) = {\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G_2,R) = -\infty$, then we set ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace} (G_1,G_2):=0$ (note that any fixed integer would satisfy the first condition in Definition \[defi:equiv\]). Following the notation of Bodlaender *et al*. [@BFL+09], the function ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}$ is called the *transposition function* for the equivalence relation [[${\mathcal}{E}_{}$]{}]{}. Note that we can use the restriction of ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}$ to couples of graphs in [${\mathcal}{F}_t$]{}to define the equivalence relation [[${\mathcal}{E}_{}$]{}]{}.

In the following we only consider classes of graphs whose membership can be expressed in Monadic Second Order (MSO) logic. Therefore, we know that the number of equivalence classes of [${\mathcal}{G}$]{}is finite [@Buc60], say at most $r_{{\ensuremath{{\mathcal}{G}}\xspace},t}$, and we can state the following lemma.

$[\star]$ \[lem:nb class\] Let [${\mathcal}{G}$]{}be a class of graphs whose membership is expressible in MSO logic. For any encoder [[${\mathcal}{E}_{}$]{}]{}, any function $g: \mathbb{N} \rightarrow \mathbb{N}$ and any integer $t \in \mathbb{N}$, if [[${\mathcal}{E}_{}$]{}]{}is $g$-confined then the equivalence relation [[${\mathcal}{E}_{}$]{}]{}has at most $ r({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace}):=(g(t)+2)^{s_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}(t)} \cdot 2^t \cdot r_{{\ensuremath{{\mathcal}{G}}\xspace},t} $ equivalence classes. In particular, the equivalence relation [[${\mathcal}{E}_{}$]{}]{}has at most $ r({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace})$ equivalence classes as well.

\[defi:DP-friend\] An equivalence relation [[${\mathcal}{E}_{}$]{}]{}is *DP-friendly* if, for any graph $G \in {\ensuremath{{\mathcal}{B}_t}\xspace}$ with $\partial(G) = A$ and any two boundaried graphs $H$ and $G_B$ with $G= H \oplus G_B$ such that $G_B$ has boundary $B \subseteq V(G)$ with $|B| {\leqslant}t$ and $A\cap V(G_B) \subseteq B$, the following holds. Let $G'\in {\ensuremath{{\mathcal}{B}_t}\xspace}$ with $\partial(G') = A$ be the graph obtained from $G$ by replacing the subgraph $G_B$ with some $G_B' \in {\ensuremath{{\mathcal}{B}_t}\xspace}$ such that $G_B {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace}^*}\xspace} G_B'$. Then $G {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace}^*}\xspace} G'$ and ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}(G,G') = {\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}(G_B, G_B')$.

The following useful fact states that for proving that [[${\mathcal}{E}_{}$]{}]{}is DP-friendly, it suffices to prove that $G {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}^*}\xspace} G'$ instead of $G {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace}^*}\xspace} G'$.

$[\star]$ \[fait:equiv\] Let $G\in {\ensuremath{{\mathcal}{B}_t}\xspace}$ with a separator $B$, let $G_B {\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace} G_B'$, and let $G' \in {\ensuremath{{\mathcal}{B}_t}\xspace}$ as in Definition \[defi:DP-friend\]. If $G {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}^*}\xspace} G'$, then $G {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace}^*}\xspace} G'$.

In order to perform a protrusion replacement that does not modify the behavior of the graph with respect to a problem $\Pi$, we need the relation [[${\mathcal}{E}_{}$]{}]{}to be a refinement of the canonical equivalence relation $\equiv_{\Pi,t}$.

$[\star]$\[lem:refine eq\] Let $\Pi$ be a packing-certifiable parameterized problem defined on a graph class ${\cal G}$, let [[${\mathcal}{E}_{}$]{}]{}be an encoder, let $g: \mathbb{N} \rightarrow \mathbb{N}$, and let $G_1, G_2 \in {\ensuremath{{\mathcal}{B}_t}\xspace}$. If [[${\mathcal}{E}_{}$]{}]{}is a $g$-confined $\Pi$-encoder and [[${\mathcal}{E}_{}$]{}]{}is DP-friendly, then the fact that $G_1 {\ensuremath{{\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace}^*}\xspace} G_2$ implies the following:

-   $G_1 \equiv_\Pi G_2$; and

-   $\Delta_{\Pi,t}(G_1,G_2) = {\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}(G_1,G_2)$.

In particular, this holds when $G_1, G_2 \in {\ensuremath{{\mathcal}{F}_t}\xspace}$ and $G_1 {\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace} G_2$.

\[defi:progres\] Given an encoder [[${\mathcal}{E}_{}$]{}]{}and an equivalence class $\mathfrak{C} \subseteq {\ensuremath{{\mathcal}{F}_t}\xspace}$ of [[${\mathcal}{E}_{}$]{}]{}, a graph $G \in \mathfrak{C}$ is a *progressive representative* of $\mathfrak{C}$ if for any $G'\in \mathfrak{C}$, it holds that ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}(G,G') {\leqslant}0$.

$[\star]$\[lem:progres size\] Let [${\mathcal}{G}$]{}be a class of graphs whose membership is expressible in MSO logic. For any encoder [[${\mathcal}{E}_{}$]{}]{}, any function $g: \mathbb{N} \rightarrow \mathbb{N}$, and any $t \in \mathbb{N}$, if [[${\mathcal}{E}_{}$]{}]{}is $g$-confined and [[${\mathcal}{E}_{}$]{}]{}is DP-friendly, then any equivalence class of [[${\mathcal}{E}_{}$]{}]{}has a progressive representative of size at most $b({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace}) := 2^{r({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace})+1} \cdot t$, where $r({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace})$ is the function defined in Lemma \[lem:nb class\].

**An explicit protrusion replacement.** The next lemma specifies conditions under which, given an upper bound on the size of the representatives, a generic DP algorithm can provide in linear time an explicit protrusion replacer.

$[\star]$ \[lem:comput repres\] Let [${\mathcal}{G}$]{}be a class of graphs, let [[${\mathcal}{E}_{}$]{}]{}be an encoder, let $g: \mathbb{N} \rightarrow \mathbb{N}$, and let $t \in \mathbb{N}$ such that [[${\mathcal}{E}_{}$]{}]{}is $g$-confined and [[${\mathcal}{E}_{}$]{}]{}is DP-friendly. Assume we are given an upper bound $b {\geqslant}t$ on the size of a smallest progressive representative of any class of [[${\mathcal}{E}_{}$]{}]{}. Given a $t$-protrusion $Y$ inside some graph, we can compute a $t$-protrusion $Y'$ of size at most $b$ such that $Y {\ensuremath{\sim_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},{\ensuremath{{\mathcal}{G}}\xspace},t}}\xspace} Y'$ and ${\ensuremath{\Delta_{{{\ensuremath{{\mathcal}{E}_{}}\xspace}},t}}\xspace}(Y',Y) {\leqslant}0$. Furthermore, such a protrusion can be computed in time $ O(|Y|)$, where the hidden constant depends only on ${{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,b,{\ensuremath{{\mathcal}{G}}\xspace}$, and $t$.

Let us now piece everything together to state the main result of [@KviaDP] that we need to reprove here for packing-certifiable problems. For issues of constructibility, we restrict [${\mathcal}{G}$]{}to be the class of $H$-(topological)-minor-free graphs.

$[\star]$ \[theo:main\] Let [${\mathcal}{G}$]{}be the class of graphs excluding some fixed graph $H$ as a (topological) minor and let $\Pi$ be a parameterized packing-certifiable problem defined on [${\mathcal}{G}$]{}. Let [[${\mathcal}{E}_{}$]{}]{}be an encoder, let $g: \mathbb{N} \rightarrow \mathbb{N}$, and let $t \in \mathbb{N}$ such that [[${\mathcal}{E}_{}$]{}]{}is a $g$-confined $\Pi$-encoder and [[${\mathcal}{E}_{}$]{}]{}is DP-friendly. Given an instance $(G,k)$ of $\Pi$ and a $t$-protrusion $Y$ in $G$, we can compute in time $O(|Y|)$ an equivalent instance $(G-(Y-\partial(Y)) \oplus Y',k')$ where $Y'$ is a $t$-protrusion with $|Y'| {\leqslant}b({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace})$ and $k'{\leqslant}k$ and where $b({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace})$ is the function defined in Lemma \[lem:progres size\].

Such a protrusion replacer can be used to obtain a kernel when, for instance, one is able to provide a protrusion decomposition of the instance.

$[\star]$ \[coro:main\] Let [${\mathcal}{G}$]{}be the class of graphs excluding some fixed graph $H$ as a (topological) minor and let $\Pi$ be a parameterized packing-certifiable problem defined on [${\mathcal}{G}$]{}. Let [[${\mathcal}{E}_{}$]{}]{}be an encoder, let $g: \mathbb{N} \rightarrow \mathbb{N}$, and let $t \in \mathbb{N}$ such that [[${\mathcal}{E}_{}$]{}]{}is a $g$-confined $\Pi$-encoder and [[${\mathcal}{E}_{}$]{}]{}is DP-friendly. Given an instance $(G,k)$ of $\Pi$ and an $(\alpha k,t)$-protrusion decomposition of $G$, we can construct a linear kernel for $\Pi$ of size at most $ (1+b({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace}))\cdot \alpha \cdot k$, where $b({{\ensuremath{{\mathcal}{E}_{}}\xspace}},g,t,{\ensuremath{{\mathcal}{G}}\xspace})$ is the function defined in Lemma \[lem:progres size\].

Main ideas for the applications {#sec:applications}
===============================

In this section by sketch the main ingredients that we use in our applications for obtaining the linear kernels, before going through the details for each problem in the next sections.

**<span style="font-variant:small-caps;">General methodology</span>.** The next theorem will be fundamental in the applications.

\[theo:prot dec\] Let $c,t$ be two positive integers, let $H$ be an $h$-vertex graph, let $G$ be an $n$-vertex $H$-topological-minor-free graph, and let $k$ be a positive integer. If we are given a set $X \subseteq V(G)$ with $|X| {\leqslant}c \cdot k$ such that ${{\mathbf{tw}}}(G-X) {\leqslant}t$, then we can compute in time $O(n)$ an $((\alpha_{H} \cdot t \cdot c)\cdot k, 2t + h)$-protrusion decomposition of $G$, where $\alpha_{H}$ is a constant depending only on $H$, which is upper-bounded by $40 h^2 2 ^{5 h \log h}$.

A typical application of our framework for obtaining an explicit linear kernel for a packing-certifiable problem $\Pi$ on a graph class [${\mathcal}{G}$]{}is as follows. The first task is to define an encoder ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}$ and to prove that for some function $g: \mathbb{N} \rightarrow \mathbb{N}$, [[${\mathcal}{E}_{}$]{}]{}is a $g$-confined $\Pi$-encoder and [[${\mathcal}{E}_{}$]{}]{}is DP-friendly. The next ingredient is a polynomial-time algorithm that, given an instance $(G,k)$ of $\Pi$, either reports that $(G,k)$ is a <span style="font-variant:small-caps;">Yes</span>-instance (or a <span style="font-variant:small-caps;">No</span>-instance, depending on the problem), or finds a treewidth-modulator of $G$ with size $O(k)$. The way to obtain this algorithm depends on each particular problem and in our applications we will use a number of existing results in the literature in order to find it. Once we have such a linear treewidth-modulator, we can use Theorem \[theo:prot dec\] to find a linear protrusion decomposition of $G$. Finally, it just remains to apply Corollary \[coro:main\] to obtain an explicit linear kernel for $\Pi$ on ${\ensuremath{{\mathcal}{G}}\xspace}$; see Figure \[fig:scheme\] for a schematic illustration.

Let us provide here some generic intuition about the additional criterion mentioned in the introduction to discard the entries in the tables of an encoder. For an encoder ${{\ensuremath{{\mathcal}{E}_{}}\xspace}}= ({\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace},{\ensuremath{L^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace},{\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace})$ and a function $g: \mathbb{N} \to \mathbb{N}$, we need some notation in order to define the *relevant function* [$\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}$]{}, which will be an appropriate modification of [$f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}$]{}. Let $G \in {\ensuremath{{\mathcal}{B}_t}\xspace}$ with boundary $A$ and let $R_A$ be an encoding. We (recursively) define $R_A$ to be *irrelevant for [$\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}$]{}* if there exists a certificate ${\mathcal}{S}$ such that $(G,{\mathcal}{S},R_A)\in {\ensuremath{L^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}$ and $|{\mathcal}{S}|= {\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R_A)$ and a separator $B \subseteq V(G)$ with $|B| {\leqslant}t$ and $B \neq A$, such that ${\mathcal}{S}$ [*induces*]{} an encoding $R_B$ in the graph $G_B \in {\ensuremath{{\mathcal}{B}_t}\xspace}$ with $ {\ensuremath{\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}}\xspace}(G_B,R_B) = -\infty$. Here, by using the term “induces” we implicitly assume that ${\mathcal}{S}$ defines an encoding $R_B$ in the graph $G_B$; this will be the case in all the encoders used in our applications.

To define [$\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}$]{}, we will always use the following [*natural*]{} function [$f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}$]{}, which for each problem $\Pi$ is meant to correspond to an extension to boundaried graphs of the maximization function $f^{\Pi}$ of Definition \[defi:optimization-function\]. For a graph $G$ and an encoding $R$, this natural function is defined as ${\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R)  =  \max \{k  :  \exists {\mathcal}{S}, |{\mathcal}{S}| {\geqslant}k, (G,{\mathcal}{S},R) \in {\ensuremath{L^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}\}$. Then we define the function ${\ensuremath{\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}}\xspace}$ as follows:

$$\label{eq: relevant f}
{\ensuremath{\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}}\xspace}(G,R_A) =\
\left\{\begin{array}{lll}
  & -\infty,  & \text{if } {\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R_A) + g(t) < \max \{{\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R): R \in {\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(\Lambda(G)) \}, \\
  &     &     \text{or if $R_A$ is irrelevant for {\ensuremath{\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}}\xspace}.} \\
  & {\ensuremath{f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace}(G,R_A),  & \mbox{otherwise}.\\
\end{array}\right.$$

That is, we will use the modified encoder $({\ensuremath{{\mathcal}{C}^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace},{\ensuremath{L^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}}\xspace},{\ensuremath{\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}}\xspace})$. We need to guarantee that the above function [$\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}$]{}is computable, as required[^5] in Definition \[defi:encod\]. Indeed, from the definition it follows that an encoding $R_A$ defined at a node $x$ of a given tree decomposition is irrelevant if and only if $R_A$ can be obtained by combining encodings corresponding to the children of $x$, such that at least one of them is irrelevant. This latter property can be easily computed recursively on a tree decomposition, by performing standard dynamic programming. We will omit this computability issue in the applications, as the same argument sketched here applies to all of them.

In order to obtain the linear treewidth-modulators mentioned before, we will use several results from [@BFL+09; @FLST10; @FLRS10], which in turn use the following two propositions. For an integer $r{\geqslant}2$, let ${\rm \Gamma}_{r}$ be the graph obtained from the $(r\times r)$-grid by triangulating internal faces such that all internal vertices become of degree $6$, all non-corner external vertices are of degree 4, and one corner of degree 2 is made adjacent to all vertices of the external face (the [*corners*]{} are the vertices that in the underlying grid have degree 2). As an example, the graph $\Gamma_6$ is shown in Figure \[fig-gamma-k\].

\[prop:tw-minor\] There is a function $f_m:\mathbb{N}\rightarrow\mathbb{N}$ such that for every $h$-vertex graph $H$ and every positive integer $r$, every $H$-minor-free graph with treewidth at least $f_{m}(h)\cdot r$, contains the $(r\times r)$-grid as a minor.

\[prop:tw-contraction\] There is a function $f_c:\mathbb{N}\rightarrow\mathbb{N}$ such that for every $h$-vertex apex graph $H$ and every positive integer $r$, every $H$-minor-free graph with treewidth at least $f_{c}(h)\cdot r$, contains the graph ${\rm \Gamma}_{r}$ as a contraction.

The current best upper bound [@KaKo12] for the function $f_m$ is $f_m (h) = 2^{ O(h^2  \log h)}$ and, up to date, there is no explicit bound for the function $f_c$. We would like to note that this non-existence of explicit bounds for $f_c$ is an issue that concerns the [*graph class*]{} of $H$-minor-free graphs and it is perfectly compatible with our objective of providing explicit constants for particular [*problems*]{} defined on that graph class, which will depend on the function $f_c$.

Let us now provide a sketch of the main basic ingredients used in each of the applications.

**Packing minors.** Let ${\mathcal}{F}$ be a fixed finite set of graphs. In the <span style="font-variant:small-caps;">${\mathcal}{F}$-Packing</span> problem, we are given a graph $G$ and an integer parameter $k$ and the question is whether $G$ has $k$ vertex-disjoint subgraphs $G_1,\ldots,G_k$, each containing some graph in ${\mathcal}{F}$ as a minor. When all the graphs in ${\mathcal}{F}$ are connected and ${\mathcal}{F}$ contains at least one planar graph, we call the problem <span style="font-variant:small-caps;">Connected-Planar-${\mathcal}{F}$-Packing</span>. The encoder uses the notion of rooted packing introduced by Adler *et al*. [@ADF+11], which we also used in [@KviaDP] for <span style="font-variant:small-caps;">Connected-Planar-${\mathcal}{F}$-Deletion</span>. To obtain the treewidth-modulator, we use the *Erdős-Pósa property* for graph minors [@ErPo65; @RoSe86; @ChChSTOC13]. More precisely, we use that on minor-free graphs, as proved by Fomin *et al*. [@FST11], if $(G,k)$ is a <span style="font-variant:small-caps;">No</span>-instance of <span style="font-variant:small-caps;">Connected-Planar-${\mathcal}{F}$-Packing</span>, then $(G,k')$ is a <span style="font-variant:small-caps;">Yes</span>-instance of <span style="font-variant:small-caps;">Connected-Planar-${\mathcal}{F}$-Deletion</span> for $k' = O(k)$. Finally, we use a result of Fomin *et al*. [@FLST10] that provides a polynomial-time algorithm to find treewidth-modulators for <span style="font-variant:small-caps;">Yes</span>-instances of <span style="font-variant:small-caps;">Connected-Planar-${\mathcal}{F}$-Deletion</span>. The obtained constants involve, in particular, the currently best known constant-factor approximation of treewidth on minor-free graphs.

**Packing scattered minors.** Let ${\mathcal}{F}$ be a fixed finite set of graphs and let $\ell$ be a positive integer. In the $\ell$-${\mathcal}{F}$-Packing problem, we are given a graph $G$ and an integer parameter $k$ and the question is whether $G$ has $k$ subgraphs $G_1,\ldots,G_k$ pairwise at distance at least $\ell$, each containing some graph from ${\mathcal}{F}$ as a minor. The encoder for [<span style="font-variant:small-caps;">$\ell$-$\cal F$-Packing</span>]{}is a combination of the encoder for [<span style="font-variant:small-caps;">$\cal F$-Packing</span>]{}and the one for $\ell$-<span style="font-variant:small-caps;">Scattered Set</span> that we used in [@KviaDP]. For obtaining the treewidth-modulator, unfortunately we cannot proceed as for packing minors, as up to date no linear Erdős-Pósa property for packing scattered planar minors is known; the best bound we are aware of is $O(k\sqrt{k})$, which is [*not*]{} enough to obtain a linear kernel. To circumvent this problem, we use the following trick: we (artificially) formulate [<span style="font-variant:small-caps;">$\ell$-$\cal F$-Packing</span>]{}as a vertex-certifiable problem and prove that it fits the conditions required by the framework of Fomin *et al*. [@FLST10] to produce a treewidth-modulator. (We would like to stress that this formulation of the problem as a vertex-certifiable one is [*not*]{} enough to apply the results of [@KviaDP], as one has to further verify the necessary properties of the encoder are satisfied and it does not seem to be an easy task at all.) Once we have it, we consider the original formulation of the problem to define its encoder. As a drawback of resorting to the general results of [@FLST10] and, due to the fact that [<span style="font-variant:small-caps;">$\ell$-$\cal F$-Packing</span>]{}is contraction-bidimensional, we provide linear kernels for the problem on the (smaller) class of apex-minor-free graphs. **Packing overlapping minors.** Let ${\mathcal}{F}$ be a fixed finite set of graphs and let $\ell$ be a positive integer. In the <span style="font-variant:small-caps;">$\cal F$-Packing with $\ell$-Membership</span> problem, we are given a graph $G$ and an integer parameter $k$ and the question is whether $G$ has $k$ subgraphs $ G_1,\dots,G_k$ such that each subgraph contains some graph from $\cal F$ as a minor, and each vertex of $G$ belongs to at most $\ell$ subgraphs. The encoder is an enhanced version of the one for packing minors, in which we allow a vertex to belong simultaneously to several minor-models. To obtain the treewidth-modulator, the situation is simpler than above, thanks to the fact that a packing of models is in particular a packing of models with $\ell$-membership. This allows us to use the linear Erdős-Pósa property that we described for packing minors and therefore to construct linear kernels on minor-free graphs.

**Packing scattered and overlapping subgraphs.** The definitions of the corresponding problems are similar to the ones above, just by replacing the minor by the subgraph relation. The encoders are simplified versions of those that we defined for packing scattered and overlapping minors, respectively. The idea for obtaining the treewidth-modulator is to apply a simple reduction rule that removes all vertices not belonging to any of the copies of the subgraphs we are looking for. It can be easily proved that if a reduced graph is a <span style="font-variant:small-caps;">No</span>-instance of the problem, then it is a <span style="font-variant:small-caps;">Yes</span>-instance of $\ell'$-<span style="font-variant:small-caps;">Dominating Set</span>, where $\ell'$ is a function of the integer $\ell$ corresponding to the problem and the largest diameter of a subgraph in the given family. We are now in position to use the machinery of [@FLST10] for $\ell'$-<span style="font-variant:small-caps;">Dominating Set</span> and find a linear treewidth-modulator.

Conclusions and further research {#sec:conclusions}
================================

In this article we generalized the framework introduced in [@KviaDP] to deal with packing-certifiable problems. Our main result can be seen as a [*meta-theorem*]{}, in the sense that as far a particular problem satisfies the generic conditions stated in Corollary \[coro:main\], an explicit linear kernel on the corresponding graph class follows. Nevertheless, in order to verify these generic conditions and, in particular, to verify that the equivalence relation associated with an encoder is DP-friendly, the proofs are usually quite technical and one first needs to get familiar with several definitions. We think that it may be possible to simplify the general methodology, thus improving its applicability.

Concerning the explicit bounds derived from our results, one natural direction is to reduce them as much as possible. These bounds depend on a number of intermediate results that we use along the way and improving any of them would result in an improvement on the overall kernel sizes. It is worth insisting here that some of the bounds involve the (currently) [*non-explicit*]{} function $f_c$ defined in Proposition \[prop:tw-contraction\], which depends exclusively on the considered graph class (and not on each particular problem). In order to find explicit bounds for this function $f_c$, we leave as future work using the linear-time deterministic protrusion replacer recently introduced by Fomin *et al*. [@FLM+15], partially inspired from [@KviaDP].

**Acknowledgement.** We would like to thank Archontia C. Giannopoulou for insightful discussions about the Erdős-Pósa property for scattered planar minors.

[^1]: AlGCo project-team, CNRS, LIRMM, Université de Montpellier, Montpellier, France.

[^2]: Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece.

[^3]: [Emails: Valentin Garnero: [valentin.garnero@inria.fr]{}, Christophe Paul: [paul@lirmm.fr]{}, Ignasi Sau: [sau@lirmm.fr]{}, Dimitrios M. Thilikos: [sedthilk@thilikos.info]{}]{}.

[^4]: We would like to clarify here that in our original conference submission of [@KviaDP] we claimed, among other results, a linear kernel for <span style="font-variant:small-caps;">${\mathcal F}$-Packing</span> on sparse graphs. Unfortunately, while preparing the camera-ready version, we realized that there was a bug in one of the proofs and we had to remove that result from the paper. It turned out that for fixing that bug, several new ideas and a generalization of the original framework seemed to be necessary; this was the starting point of the results presented in the current article.

[^5]: The fact that the values of the function [$\bar f^{{{\ensuremath{{\mathcal}{E}_{}}\xspace}}}_{g}$]{}can be calculated is important, in particular, in the proof of Lemma \[lem:comput repres\], since we need to be able to compute equivalence classes of the equivalence relation [[${\mathcal}{E}_{}$]{}]{}.
