Explicit linear kernels for packing problems∗
Valentin Garnero†
Christophe Paul†
Dimitrios M. Thilikos†‡

Ignasi Sau†

arXiv:1610.06131v1 [] 19 Oct 2016

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. F-Packing is a typical
example: for a family 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 F as a minor. We provide explicit
linear kernels on sparse graphs for the following two orthogonal generalizations of
F-Packing: for an integer ` > 1, one aims at finding either minor-models that are
pairwise at distance at least ` in G (`-F-Packing), or such that each vertex in G
belongs to at most ` minors-models (F-Packing with `-Membership). Finally,
we also provide linear kernels for the versions of these problems where one wants to
pack subgraphs instead of minors.

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

1

Introduction

Motivation. A fundamental notion in parameterized complexity (see [10] 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)
∗
Emails: Valentin Garnero: valentin.garnero@inria.fr, Christophe Paul: paul@lirmm.fr, Ignasi Sau:
sau@lirmm.fr, Dimitrios M. Thilikos: sedthilk@thilikos.info.
†
AlGCo project-team, CNRS, LIRMM, Université de Montpellier, Montpellier, France.
‡
Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece.

1

is one of the major goals of this area. A pioneering work in this direction was the linear
kernel of Alber et al. [2] for Dominating Set on planar graphs, generalized by Guo and
Niedermeier [24] to a family of problems on planar graphs. Several algorithmic metatheorems on kernelization have appeared in the last years, starting with the result of
Bodlaender et al. [5] on graphs of bounded genus. It was followed-up by similar results
on larger sparse graph classes, such as graphs excluding a minor [20] or a topological
minor [26].
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 [22] 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 [5, 20, 26] 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 [22] 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-Dominating Set or
Planar-F-Deletion.
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 [22] 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 Cycle Packing, is FPT as it
is minor-closed, but it is unlikely to admit polynomial kernels on general graphs [6].
As an illustrative example, for a family of connected graphs F containing at least one
planar graph, we provide a linear kernel on sparse graphs for the F-Packing problem1 :
decide whether a graph G contains at least k vertex-disjoint subgraphs such that each of
them contains a graph in F as a minor, parameterized by k. We provide linear kernels
as well for the following two orthogonal generalizations of F-Packing: for an integer
` > 1, one aims at finding either minor-models that are pairwise at distance at least
` in G (`-F-Packing), or such that each vertex in G belongs to at most ` minorsmodels (F-Packing with `-Membership). While only the existence of linear kernels
for F-Packing was known [5], to the best of our knowledge no kernels were known for
`-F-Packing and F-Packing with `-Membership, except for `-F-Packing when F
1

We would like to clarify here that in our original conference submission of [22] we claimed, among
other results, a linear kernel for F-Packing 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.

2

consists only of a triangle and the maximum degree is also considered as a parameter [3].
We would like to note that the kernels for F-Packing and for F-Packing with `Membership apply to minor-free graphs, while those for `-F-Packing for ` > 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 `-FSubgraph-Packing and F-Subgraph-Packing with `-Membership. While the first
problem can be seen as a broad generalization of `-Scattered Set (see for instance [5,
22]), the second one was recently defined by Fernau et al. [16], motivated by the problem
of discovering overlapping communities (see also [32, 33] for related problems about
detecting overlapping communities): the parameter ` 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 F such that every vertex in V (G)
belongs to at most ` subgraphs. This type of overlap was also studied by Fellows et
al. [15] in the context of graph editing. Fernau et al. [16] proved, in particular, that the
F-Subgraph-Packing with `-Membership problem is NP-hard for all values of ` > 1
when F = {F } and F is an arbitrary connected graph with at least three vertices, but
polynomial-time solvable for smaller graphs. Note that F-Subgraph-Packing with `Membership generalizes the F-Subgraph-Packing problem, which consists in finding
in a graph G at least k vertex-disjoint subgraphs isomorphic to a member of F. The
smallest kernel for the F-Subgraph-Packing problem [29] has size O(k r−1 ), where
F = {F } and F is an arbitrary graph on r vertices. A list of references of kernels for
particular cases of the family F can be found in [16]. Concerning the kernelization of
F-Subgraph-Packing with `-Membership, Fernau et al. [16] 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 F. In this article we improve this result on graphs excluding a fixed graph as
a minor, by providing a linear kernel for F-Subgraph-Packing with `-Membership
when 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 [11, 28], 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 [22] 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 E needs to satisfy
3

in order to obtain an explicit linear kernel for a parameterized problem Π.
The first natural condition is that on a graph G without boundary, the optimal size
of the objects satisfying the constraints imposed by E coincides with the optimal size of
solutions of Π in G; in that case we say that E is a Π-encoder. On the other hand, we
need that when performing DP using the encoding E, 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 E is g-confined. Finally, the third condition
requires that E 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 E 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 3, with an encoding E we associate
a function f E that corresponds, roughly speaking, to the maximum size of a partial
solution that satisfies the constraints defined by E. In order for an encoder to be gconfined for some function g(t) of the treewidth t, for some vertex-certifiable problems
such as r-Scattered Set (see [22]) 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 F-Packing. 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 Ω(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 2,
including graph minors, parameterized problems, (rooted) tree decompositions, boundaried graphs, the canonical equivalence relation ≡Π,t for a problem Π 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 [5, 20, 22, 26]. In Section 3 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 [22], for better readability we moved the
4

proofs of the results marked with ‘[?]’ to Appendix A. Before moving to the details of
each particular problem, in Section 4 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 5 with the
linear kernel for Connected-Planar-F-Packing. 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 6 we deal with the
variant in which the minor-models are pairwise at distance at least `, and in Section 7
with the version in which each vertex can belong to at most ` minor-models. In Section 8
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 9 concludes the
article.

2

Preliminaries

In our article graphs are undirected, simple, and without loops. We use standard graphtheoretic notation; see for instance [13]. We denote by dG (v, w) the distance in G between
two vertices v and w and by dG (W1 , W2 ) = min{dG (w1 , w2 ) : w1 ∈ W1 , w2 ∈ W2 } the
distance between two sets of vertices W1 and W2 of G. Given S ⊆ V (G), we denote by
N (S) the set of vertices in V (G) \ S having at least one neighbor in S.
Definition 1. A parameterized graph problem Π is called packing-certifiable if there
exists a language LΠ (called certifying language for Π) defined on pairs (G, S), where G
is a graph and S is a collection of subgraphs of G, such that (G, k) is a Yes-instance
of Π if and only if there exists a collection S of subgraphs of G with |S| > k such that
(G, S) ∈ LΠ .
In the above definition, for the sake of generality we do not require the subgraphs in
the collection S to be pairwise distinct. Also, note that the subclass of packing-certifiable
problems where each subgraph in S is restricted to consist of a single vertex corresponds
to the class of vertex-certifiable problems defined in [22].
For a class of graphs G, we denote by ΠG the problem Π where the instances are
restricted to contain graphs belonging to G. With a packing-certifiable problem we can
associate in a natural way an optimization function as follows.
Definition 2. Given a packing-certifiable parameterized problem Π, the maximization
function f Π : Γ∗ → N ∪ {−∞} is defined as

max{|S| : (G, S) ∈ LΠ } , if there exists such an S and
Π
f (G) =
(1)
−∞
, otherwise.
Definition 3. A boundaried graph is a graph G with a set B ⊆ V (G) of distinguished
vertices and an injective labeling λG : B → N. The set B is called the boundary of G
5

and it is denoted by ∂(G). The set of labels is denoted by Λ(G) = {λG (v) : v ∈ ∂(G)}.
We say that a boundaried graph is a t-boundaried graph if Λ(G) ⊆ {1, . . . , t}.
We denote by Bt the set of all t-boundaried graphs.
Definition 4. Let G1 and G2 be two boundaried graphs. We denote by G1 ⊕G2 the graph
obtained from G by taking the disjoint union of G1 and G2 and identifying vertices with
the same label in the boundaries of G1 and G2 . In G1 ⊕ G2 there is an edge between two
labeled vertices if there is an edge between them in G1 or in G2 .
Given G = G1 ⊕ G2 and G02 , we say that G0 = G1 ⊕ G02 is the graph obtained from G
by replacing G2 with G02 . The following notion was introduced by Bodlaender el al. [5].
Definition 5. Let Π be a parameterized problem and let t ∈ N. Given G1 , G2 ∈ Bt ,
we say that G1 ≡Π G2 if Λ(G1 ) = Λ(G2 ) and there exists a transposition constant
∆Π,t (G1 , G2 ) ∈ Z such that for every H ∈ Bt and every k ∈ Z, it holds that (G1 ⊕H, k) ∈
Π if and only if (G2 ⊕ H, k + ∆Π,t (G1 , G2 )) ∈ Π.
Definition 6. A tree decomposition of a graph G is a couple (T, X = {Bx : x ∈ V (T )}),
S
where T is a tree and such that x∈V (T ) Bx = V (G), for every edge {u, v} ∈ E(G) there
exists x ∈ V (T ) such that u, v ∈ Bx , and for every vertex u ∈ V (G) the set of nodes
{x ∈ V (T ) : u ∈ Bx } induce a subtree of T . The vertices of T are referred to as nodes
and the sets Bx are called bags.
A rooted tree decomposition (T, X , r) is a tree decomposition with a distinguished
node r selected as the root. A nice tree decomposition (T, X , r) (see [27]) is a rooted
tree decomposition where T is binary and for each node x with two children y, z it holds
Bx = By = Bz and for each node x with one child y it holds Bx = By ∪ {u} or
Bx = By \ {u} for some u ∈ V (G). The width of a tree decomposition is the size of a
largest bag minus one. The treewidth of a graph, denoted by tw(G), is the smallest width
of a tree decomposition of G. A treewidth-modulator of a graph G is a set X ⊆ V (G)
such that tw(G − X) 6 t, for some fixed constant t.
Given a bag B (resp. a node x) of a rooted tree decomposition T , we denote by
GB (resp. Gx ), 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 Ft 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 Ft ⊆ Bt . (Note that graphs
can be viewed as 0-boundaried graphs, hence we use a same alphabet Γ for describing
graphs and boundaried graphs.)
Definition 7. Let t, α be positive integers. A t-protrusion Y of a graph G is an induced
subgraph of G with |∂(Y )| 6 t and tw(Y ) 6 t − 1, where ∂(Y ) is the set of vertices of
Y having neighbors in V (G) \ V (Y ). An (α, t)-protrusion decomposition of a graph G
is a partition P = Y0 ] Y1 ] · · · ] Y` of V (G) such that for every 1 6 i 6 `, N (Yi ) ⊆ Y0 ,
max{`, |Y0 |} 6 α, and for every 1 6 i 6 `, Yi ∪N (Yi ) is a t-protrusion of G. When (G, k)
6

is the input of a parameterized problem with parameter k, we say that an (α, t)-protrusion
decomposition of G is linear whenever α = O(k).
We say that a rooted tree decomposition of a protrusion G (resp. a boundaried graph
G) is boundaried if the boundary ∂(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 [4, 27].

3

A framework to replace protrusions for packing problems

In this section we restate and in many cases modify the definitions given in [22] 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 A.
Encoders. In the following we extend the definition of an encoder given in [22, Definition
3.2] so that it is able to deal with packing-certifiable problems. The main difference is
that now the function f E 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 “−∞”) 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 E , so that encoders can indeed be used for performing dynamic programming.
Definition 8. An encoder is a triple E = (C E , LE , f E ) where
∗

C E is a function in 2N → 2Υ that maps a finite subset of integers I ⊆ N to a set C E (I)
of strings over some alphabet Υ. Each string R ∈ C E (I) is called an encoding. The
size of the encoder is the function sE : N → N defined as sE (t) := max{|C E (I)| :
I ⊆ {1, . . . , t}}, where |C E (I)| denotes the number of encodings in C E (I);
LE is a computable language which accepts triples (G, S, R) ∈ Γ∗ × Σ∗ × Υ∗ , where G
is a boundaried graph, S is a collection of subgraphs of G and R ∈ C E (Λ(G)) is an
encoding. If (G, S, R) ∈ LE , we say that S satisfies the encoding R in G; and
f E is a computable function in Γ∗ × Υ∗ → N ∪ {−∞} that maps a boundaried graph
G and an encoding R ∈ C E (Λ(G)) to an integer or to −∞.
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 packingcertifiable problem Π by doing DP over a tree decomposition of the input graph. The
encodings in C E (I) correspond to the entries of the DP-tables of graphs with boundary
labeled by the set of integers I. The language LE identifies certificates which are partial
solutions satisfying the boundary conditions imposed by an encoding.
7

The following definition differs from [22, Definition 3.3] as now the function f E is
incorporated in the definition of an encoder E.
Definition 9. Let Π be a packing-certifiable problem. An encoder E is a Π-encoder
if C E (∅) is a singleton, denoted by {R∅ }, such that for any 0-boundaried graph G,
f E (G, R∅ ) = f Π (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 [5,
20, 26].
Definition 10. An encoder E is g-confined if there exists a function g : N → N such that
for any t-boundaried graph G with Λ(G) = I it holds that either {R ∈ C E (I) : f E (G, R) 6=
−∞} = ∅ or maxR {f E (G, R) 6= −∞} − minR {f E (G, R) 6= −∞} 6 g(t).
For an encoder E and a function g, in the next sections we will denote the relevant
functions discussed before by f¯gE to distinguish them from other functions that we will
need.
Equivalence relations and representatives. We now define some equivalence relations on t-boundaried graphs.
Definition 11. Let E be an encoder, let G1 , G2 ∈ Bt , and let G be a class of graphs.
1. G1 ∼∗E,t G2 if Λ(G1 ) = Λ(G2 ) =: I and there exists an integer ∆E,t (G1 , G2 ) (depending on G1 , G2 ) such that for any encoding R ∈ C E (I) we have f E (G1 , R) =
f E (G2 , R) − ∆E,t (G1 , G2 ).
2. G1 ∼G,t G2 if either G1 ∈
/ G and G2 ∈
/ G, or G1 , G2 ∈ G and, for any H ∈ Bt ,
H ⊕ G1 ∈ G if and only if H ⊕ G2 ∈ G.
3. G1 ∼∗E,G,t G2 if G1 ∼∗E,t G2 and G1 ∼G,t G2 .
4. If we restrict the graphs G1 , G2 to be in Ft , then the corresponding equivalence
relations, which are a restriction of ∼∗E,t and ∼∗E,G,t , are denoted by ∼E,t and ∼E,G,t ,
respectively.
If for all encodings R, f E (G1 , R) = f E (G2 , R) = −∞, then we set ∆E,t (G1 , G2 ) := 0
(note that any fixed integer would satisfy the first condition in Definition 11). Following
the notation of Bodlaender et al. [5], the function ∆E,t is called the transposition function
for the equivalence relation ∼∗E,t . Note that we can use the restriction of ∆E,t to couples
of graphs in Ft to define the equivalence relation ∼E,t .
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 ∼G,t is finite [7], say at most rG,t , and we can state the following
lemma.
8

Lemma 1. [?] Let G be a class of graphs whose membership is expressible in MSO logic.
For any encoder E, any function g : N → N and any integer t ∈ N, if E is g-confined
then the equivalence relation ∼∗E,G,t has at most r(E, g, t, G) := (g(t) + 2)sE (t) · 2t · rG,t
equivalence classes. In particular, the equivalence relation ∼E,G,t has at most r(E, g, t, G)
equivalence classes as well.
Definition 12. An equivalence relation ∼∗E,G,t is DP-friendly if, for any graph G ∈ Bt
with ∂(G) = A and any two boundaried graphs H and GB with G = H ⊕ GB such
that GB has boundary B ⊆ V (G) with |B| 6 t and A ∩ V (GB ) ⊆ B, the following
holds. Let G0 ∈ Bt with ∂(G0 ) = A be the graph obtained from G by replacing the
subgraph GB with some G0B ∈ Bt such that GB ∼∗E,G,t G0B . Then G ∼∗E,G,t G0 and
∆E,t (G, G0 ) = ∆E,t (GB , G0B ).
The following useful fact states that for proving that ∼∗E,G,t is DP-friendly, it suffices
to prove that G ∼∗E,t G0 instead of G ∼∗E,G,t G0 .
Fact 1. [?] Let G ∈ Bt with a separator B, let GB ∼E,G,t G0B , and let G0 ∈ Bt as in
Definition 12. If G ∼∗E,t G0 , then G ∼∗E,G,t G0 .
In order to perform a protrusion replacement that does not modify the behavior of
the graph with respect to a problem Π, we need the relation ∼∗E,t to be a refinement of
the canonical equivalence relation ≡Π,t .
Lemma 2. [?] Let Π be a packing-certifiable parameterized problem defined on a graph
class G, let E be an encoder, let g : N → N, and let G1 , G2 ∈ Bt . If E is a g-confined Πencoder and ∼∗E,G,t is DP-friendly, then the fact that G1 ∼∗E,G,t G2 implies the following:
• G1 ≡Π G2 ; and
• ∆Π,t (G1 , G2 ) = ∆E,t (G1 , G2 ).
In particular, this holds when G1 , G2 ∈ Ft and G1 ∼E,G,t G2 .
Definition 13. Given an encoder E and an equivalence class C ⊆ Ft of ∼E,G,t , a graph
G ∈ C is a progressive representative of C if for any G0 ∈ C, it holds that ∆E,t (G, G0 ) 6 0.
Lemma 3. [?] Let G be a class of graphs whose membership is expressible in MSO logic.
For any encoder E, any function g : N → N, and any t ∈ N, if E is g-confined and ∼∗E,G,t
is DP-friendly, then any equivalence class of ∼E,G,t has a progressive representative of
size at most b(E, g, t, G) := 2r(E,g,t,G)+1 · t, where r(E, g, t, G) is the function defined in
Lemma 1.
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.

9

Lemma 4. [?] Let G be a class of graphs, let E be an encoder, let g : N → N, and let
t ∈ N such that E is g-confined and ∼∗E,G,t is DP-friendly. Assume we are given an upper
bound b > t on the size of a smallest progressive representative of any class of ∼E,G,t .
Given a t-protrusion Y inside some graph, we can compute a t-protrusion Y 0 of size at
most b such that Y ∼E,G,t Y 0 and ∆E,t (Y 0 , Y ) 6 0. Furthermore, such a protrusion can
be computed in time O(|Y |), where the hidden constant depends only on E, g, b, G, and t.
Let us now piece everything together to state the main result of [22] that we need to
reprove here for packing-certifiable problems. For issues of constructibility, we restrict
G to be the class of H-(topological)-minor-free graphs.
Theorem 1. [?] Let G be the class of graphs excluding some fixed graph H as a (topological) minor and let Π be a parameterized packing-certifiable problem defined on G. Let
E be an encoder, let g : N → N, and let t ∈ N such that E is a g-confined Π-encoder and
∼∗E,G,t is DP-friendly. Given an instance (G, k) of Π and a t-protrusion Y in G, we can
compute in time O(|Y |) an equivalent instance (G − (Y − ∂(Y )) ⊕ Y 0 , k 0 ) where Y 0 is
a t-protrusion with |Y 0 | 6 b(E, g, t, G) and k 0 6 k and where b(E, g, t, G) is the function
defined in Lemma 3.
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.
Corollary 1. [?] Let G be the class of graphs excluding some fixed graph H as a (topological) minor and let Π be a parameterized packing-certifiable problem defined on G. Let
E be an encoder, let g : N → N, and let t ∈ N such that E is a g-confined Π-encoder and
∼∗E,G,t is DP-friendly. Given an instance (G, k) of Π and an (αk, t)-protrusion decomposition of G, we can construct a linear kernel for Π of size at most (1 + b(E, g, t, G)) · α · k,
where b(E, g, t, G) is the function defined in Lemma 3.

4

Main ideas for the 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.
General methodology. The next theorem will be fundamental in the applications.
Theorem 2 (Kim et al. [26]). 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 ⊆ V (G) with |X| 6 c · k such that tw(G − X) 6 t, then we can
compute in time O(n) an ((αH · t · c) · k, 2t + h)-protrusion decomposition of G, where
αH is a constant depending only on H, which is upper-bounded by 40h2 25h log h .
A typical application of our framework for obtaining an explicit linear kernel for
a packing-certifiable problem Π on a graph class G is as follows. The first task is to
define an encoder E and to prove that for some function g : N → N, E is a g-confined
10

Π-encoder and ∼∗E,G,t is DP-friendly. The next ingredient is a polynomial-time algorithm
that, given an instance (G, k) of Π, either reports that (G, k) is a Yes-instance (or a
No-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 2 to find a linear
protrusion decomposition of G. Finally, it just remains to apply Corollary 1 to obtain
an explicit linear kernel for Π on G; see Figure 1 for a schematic illustration.
Algorithm with two
possible outputs given
an instance (G, k) of
a problem Π defined
on a graph class G

(G, k) is a
Yes/No-instance
Treewidth-modulator
of size O(k)

Π-encoder
confined + DP-friendly
Theo. 2

Linear
protrusion decomposition

Coro. 1

Linear kernel
for Π on G

Figure 1: Illustration of a typical application of the framework presented in this article.
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
E = (C E , LE , f E ) and a function g : N → N, we need some notation in order to define the
relevant function f¯gE , which will be an appropriate modification of f E . Let G ∈ Bt with
boundary A and let RA be an encoding. We (recursively) define RA to be irrelevant for
f¯gE if there exists a certificate S such that (G, S, RA ) ∈ LE and |S| = f E (G, RA ) and
a separator B ⊆ V (G) with |B| 6 t and B 6= A, such that S induces an encoding RB
in the graph GB ∈ Bt with f¯gE (GB , RB ) = −∞. Here, by using the term “induces” we
implicitly assume that S defines an encoding RB in the graph GB ; this will be the case
in all the encoders used in our applications.
To define f¯gE , we will always use the following natural function f E , which for each
problem Π is meant to correspond to an extension to boundaried graphs of the maximization function f Π of Definition 2. For a graph G and an encoding R, this natural
function is defined as f E (G, R) = max{k : ∃S, |S| > k, (G, S, R) ∈ LE }. Then we define
the function f¯gE as follows:

f¯gE (G, RA ) =





if f E (G, RA ) + g(t) < max{f E (G, R) : R ∈ C E (Λ(G))},
or if RA is irrelevant for f¯gE .
f E (G, RA ), otherwise.

−∞,

That is, we will use the modified encoder (C E , LE , f¯gE ). We need to guarantee that the
above function f¯gE is computable, as required2 in Definition 8. Indeed, from the definition
it follows that an encoding RA defined at a node x of a given tree decomposition is
The fact that the values of the function f¯gE can be calculated is important, in particular, in the proof
of Lemma 4, since we need to be able to compute equivalence classes of the equivalence relation ∼E,G,t .
2

11

irrelevant if and only if RA 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 [5, 19, 20], which in turn use the following two propositions. For
an integer r > 2, let Γr be the graph obtained from the (r × 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 Γ6 is shown in Figure 2.

Figure 2: The graph Γ6 .
Proposition 1 (Demaine and Hajiaghayi [12]). There is a function fm : N → N such
that for every h-vertex graph H and every positive integer r, every H-minor-free graph
with treewidth at least fm (h) · r, contains the (r × r)-grid as a minor.
Proposition 2 (Fomin et al. [17]). There is a function fc : N → N such that for
every h-vertex apex graph H and every positive integer r, every H-minor-free graph with
treewidth at least fc (h) · r, contains the graph Γr as a contraction.
2

The current best upper bound [25] for the function fm is fm (h) = 2O(h log h) and,
up to date, there is no explicit bound for the function fc . We would like to note that
this non-existence of explicit bounds for fc 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 fc .
Let us now provide a sketch of the main basic ingredients used in each of the applications.

12

Packing minors. Let F be a fixed finite set of graphs. In the F-Packing problem,
we are given a graph G and an integer parameter k and the question is whether G has
k vertex-disjoint subgraphs G1 , . . . , Gk , each containing some graph in F as a minor.
When all the graphs in F are connected and F contains at least one planar graph, we call
the problem Connected-Planar-F-Packing. The encoder uses the notion of rooted
packing introduced by Adler et al. [1], which we also used in [22] for ConnectedPlanar-F-Deletion. To obtain the treewidth-modulator, we use the Erdős-Pósa
property for graph minors [8, 14, 30]. More precisely, we use that on minor-free graphs,
as proved by Fomin et al. [21], if (G, k) is a No-instance of Connected-PlanarF-Packing, then (G, k 0 ) is a Yes-instance of Connected-Planar-F-Deletion for
k 0 = O(k). Finally, we use a result of Fomin et al. [20] that provides a polynomial-time
algorithm to find treewidth-modulators for Yes-instances of Connected-Planar-FDeletion. The obtained constants involve, in particular, the currently best known
constant-factor approximation of treewidth on minor-free graphs.
Packing scattered minors. Let F be a fixed finite set of graphs and let ` be a positive
integer. In the `-F-Packing problem, we are given a graph G and an integer parameter
k and the question is whether G has k subgraphs G1 , . . . , Gk pairwise at distance at
least `, each containing some graph from F as a minor. The encoder for `-F-Packing
is a combination of the encoder for F-Packing and the one for `-Scattered Set
that we used in [22]. For obtaining the treewidth-modulator, unfortunately we cannot
proceed as for packing minors, as up to date no linear Erdős-Pósa property
√ for packing
scattered planar minors is known; the best bound we are aware of is O(k k), which is
not enough to obtain a linear kernel. To circumvent this problem, we use the following
trick: we (artificially) formulate `-F-Packing as a vertex-certifiable problem and prove
that it fits the conditions required by the framework of Fomin et al. [20] 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 [22], 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 [20] and, due
to the fact that `-F-Packing is contraction-bidimensional, we provide linear kernels for
the problem on the (smaller) class of apex-minor-free graphs.
Packing overlapping minors. Let F be a fixed finite set of graphs and let ` be
a positive integer. In the F-Packing with `-Membership problem, we are given a
graph G and an integer parameter k and the question is whether G has k subgraphs
G1 , . . . , Gk such that each subgraph contains some graph from F as a minor, and each
vertex of G belongs to at most ` 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
`-membership. This allows us to use the linear Erdős-Pósa property that we described
13

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 treewidthmodulator 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 No-instance of the problem, then it is a Yes-instance of `0 Dominating Set, where `0 is a function of the integer ` 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 [20] for `0 -Dominating Set and find a linear treewidth-modulator.

5

A linear kernel for Connected-Planar-F-Packing

Let F be a finite set of graphs. We define the F-Packing problem as follows.
F-Packing
Instance:
Parameter:
Question:

A graph G and a non-negative integer k.
The integer k.
Does G have k vertex-disjoint subgraphs G1 , . . . , Gk
each containing some graph in F as a minor?

In order to build a protrusion decomposition for instances of the above problem,
we use a version of the Erdős-Pósa property (see Definition 16 and Theorem 3) that
establishes a linear relation between No-instances of F-Packing and Yes-instances of
F-Deletion, and then we apply tools of Bidimensionality theory on F-Deletion (see
Corollary 2). Hence, we also need to define the F-Deletion problem.
F-Deletion
Instance:
Parameter:
Question:

A graph G and a non-negative integer k.
The integer k.
Does G have a set S ⊆ V (G) such that |S| 6 k
and G − S is H-minor-free for every H ∈ F?

When all the graphs in F are connected, the corresponding problems are called
Connected-F-Packing and Connected-F-Deletion, and when F contains at least
one planar graph, we call them Planar-F-Packing and Planar-F-Deletion, respectively. When both conditions are satisfied, the problems are called ConnectedPlanar-F-Packing and Connected-Planar-F-Deletion (the parameterized versions of these problems are respectively denoted by cFP, cFD, pFP, pFD, cpFP, and
cpFD).

14

In this section we present a linear kernel for Connected-Planar-F-Packing on
the family of graphs excluding a fixed graph H as a minor.
We need to define which kind of structure a certificate for F-Packing is. For an
arbitrary graph, a solution will consist of a packing of models as defined below. We also
recall the definition of model.
Definition 14. A model of a graph F in a graph G is a mapping Φ that assigns to
every vertex v ∈ V (F ) a non-empty connected subgraph Φ(v) of G, and to every edge
e ∈ E(F ) an edge Φ(e) ∈ E(G), such that:
• the graphs Φ(v) for v ∈ V (F ) are mutually vertex-disjoint and the edges Φ(e) for
e ∈ E(F ) are pairwise distinct;
• for {u, v} ∈ E(F ), Φ({u, v}) has one endpoint in V (Φ(u)) and the other in
V (Φ(v)).
We denote by Φ(F ) the subgraph of G obtained by the (disjoint) union of the subgraphs
Φ(v) for v ∈ V (F ) plus the edges Φ(e) for e ∈ E(F ).
Definition 15. Given a set F of minors and a graph G, a packing of models S is a
set of vertex-disjoint models. That is, the graphs Φ(F ) for Φ ∈ S, F ∈ F are pairwise
vertex-disjoint.

5.1

A protrusion decomposition for an instance of F-Packing

In order to find a linear protrusion decomposition, we need some preliminaries.
Definition 16. A class of graphs F satisfies the Erdős-Pósa property [14] if there exists
a function f such that, for every integer k and every graph G, either G contains k vertexdisjoint subgraphs each isomorphic to a graph in F, or there is a set S ⊆ V (G) of at
most f (k) vertices such that G − S has no subgraph in F.
Given a connected graph F , let M(F ) be the class of graphs that can be contracted
to F . Robertson and Seymour [30] proved that M(F ) satisfies the Erdős-Pósa property
if and only if F is planar. A significant improvement on the function f (k) has been
recently provided by Chekuri and Chuzhoy [8]. When G belongs to a proper minorclosed family, Fomin et al. [21] proved that f can be taken to be linear for any planar
graph F . It is not difficult to see that these results also hold if instead of a connected
planar graph F , we consider a finite family F of connected graphs containing at least
one planar graph. This discussion can be summarized as follows, with a precise upper
bound on the desired linear constant.
Theorem 3 (Fomin et al. [21]). Let F be a finite family of connected graphs containing
at least one planar graph on r vertices, let H be an h-vertex graph, and let G be the class
of H-minor-free graphs. There exists a constant c such that if (G, k) ∈
/ cpFPG , then
(G, c · r · 215h+8h log h · k) ∈ cpFDG .
15

The next theorem provides a way to find a treewidth-modulator for an instance of
a problem verifying the so-called bidimensionality and separability properties restricted
to the class of (apex)-minor-free graphs. Loosely speaking, the algorithm consists in
building a tree decomposition of the instance, then finding a bag that separates the
instance in such a way that the solution is balanced, and finally finding recursively other
bags in the two new tree decompositions. In order to make the algorithm constructive,
we need to build a tree decomposition of the input graph whose width differs from the
optimal one by a constant factor. To this aim, we use a (polynomial) approximation
algorithm of treewidth on minor-free graphs, which is well-known to exist. Let us denote
by τH this approximation ratio. To the best of our knowledge there is no explicit
upper bound on this ratio, but one can be derived from the proofs of Demaine and
Hajiaghayi [12]. We note that any improvement on this constant will directly translate
to the size of our kernels. We also need to compute an initial solution of the problem
under consideration. Fortunately, for all our applications, there is an EPTAS on minorfree graphs [19]. By choosing the approximation ratio of the solution to be 2, we can
announce the following theorem adapted from Fomin et al. [20].
Theorem 4 (Fomin et al. [20]). For any real ε > 0 and any minor-bidimensional (resp.
contraction-bidimensional) linear-separable problem Π on the class G of graphs that exclude a minor H (resp. an apex-minor H), there exists an integer t > 0 such that any
graph G ∈ G has a treewidth-t-modulator of size at most ε · f Π (G).
The impact of the tree decomposition approximation is hidden in the value of t,
and the impact of the solution approximation will be hidden in the “O” notation. The
parameters from the class of graphs or from the problem will affect the time complexity
of the algorithm, and not the size of our kernel. In our applications we state corollaries
of the above result (namely, Corollary 2 and Corollary 3) in which we choose ε = 1 and
we provide an explicit bound on the value of t.
We are in position to state the following corollary claiming that, given an instance of
Planar-F-Deletion, in polynomial time we can either find a treewidth-modulator or
report that is a No-instance. This is a corollary of the result of Fomin et al. [20] stated
in Theorem 4, where ε is fixed to be 1. The bound on the treewidth is derived from the
proof of Theorem 4 in [20].
Corollary 2. Let F be a finite set of graphs containing at least one r-vertex planar
graph F , let H be an h-vertex graph, and let G be the class of H-minor-free graphs. If
(G, k 0 ) ∈ pFDG , then there exists a set X ⊆ V (G) such that |X| = k 0 and tw(G − X) =
√
3 · f (h)3 ). Moreover, given an instance (G, k) with |V (G)| = n, there is an
O(r r · τH
m
algorithm running in time O(n3 ) that either finds such a set X or correctly reports that
(G, k) ∈
/ pFDG .
Note that since in Theorem 4 the value of ε can be chosen arbitrarily, we can state
many variants of the above corollary. For instance, in our previous article [22], we used
the particular case where |X| = O(r · fm (h) · k 0 ) and tw(G − X) = O(r · fm (h)2 ).
We are now able to construct a linear protrusion decomposition.
16

Lemma 5. Let F be a finite set of graphs containing at least one r-vertex planar graph
F , let H be an h-vertex graph, and let G be the class of H-minor-free graphs. Let (G, k)
be an instance of Connected-Planar-F-Packing. If (G, k) ∈
/ cpFPG , then we can
construct in polynomial time a linear protrusion decomposition of G.
Proof. Given an instance (G, k) of cpFPG , we run the algorithm given by Corollary 2 for
the Connected-Planar-F-Deletion problem with input (G, k 0 = c·r·215h+8h log h ·k).
If the algorithm is not able to find a treewidth-modulator X of size |X| = k 0 , then by
Theorem 3 we can conclude that (G, k) ∈ cpFPG . Otherwise, we use the set X as input
to the algorithm given by Theorem 2, which outputs in linear time an ((αH ·t)·k 0 , 2t+h)protrusion decomposition of G, where
√
3 · f (h)3 ) is provided by Corollary 2 (the bound on the treewidth);
• t = O(r r · τH
m
• k 0 = O(r · 2O(h log h) · k) is provided by Theorem 3 (the parameter of F-Deletion);
and
• αH = O(h2 2O(h log h) ) is the constant provided by Theorem 2.


3 · f (h)3 ) · k, O(r √r · τ 3 · f (h)3 ) That is, we obtained an O(h2 2O(h log h) · r5/2 · τH
m
m
H
protrusion decomposition of G, as claimed.

5.2

An encoder for F-Packing

Our encoder EFP for F-Packing uses the notion of rooted packing [1], and is inspired
by results on the Cycle Packing problem [5].
Assume first for simplicity that F = {F } consists of a single connected graph F .
Following [1], we introduce a combinatorial object called rooted packing. These objects
are originally defined for branch decompositions, but can easily be translated to tree
decompositions. Loosely speaking, rooted packings capture how potential models of F
intersect the separator that the algorithm is processing. It is worth mentioning that the
notion of rooted packing is related to the notion of folio introduced by Robertson and
Seymour [31], but more suited to dynamic programming.
Definition 17. Let F be a connected graph. Given a set B of boundary vertices of the
input graph G, we define a rooted packing of B as a quintuple (A, SF∗ , SF , ψ, χ), where
• SF ⊆ SF∗ are both subsets of V (F );
• A is a (possible empty) collection of mutually disjoint non-empty subsets of B;
• ψ : A → SF is a surjective mapping assigning vertices of SF to the sets in A; and
• χ : SF × SF → {0, 1} is a binary symmetric function between pairs of vertices in
SF .

17

We also define a potential model of F in G matching with (A, SF∗ , SF , ψ, χ) as a
partial mapping Φ, that assigns to every vertex v ∈ SF a non-empty subgraph Φ(v) ⊆ G
such that {A ∈ A : ψ(A) = v} is the set of intersections of B with connected components
of Φ(v); to every vertex v ∈ SF∗ \ SF a non-empty connected subgraph Φ(v) ⊆ G; and to
every edge e ∈ {e ∈ E(F ) : χ(e) = 1 ∨ e ∈ SF∗ × SF∗ \ SF } an edge Φ(e) ∈ E(G), such
that Φ satisfies the two following conditions (as in Definition 14):
• the graphs Φ(v) for v ∈ V (F ) are mutually vertex-disjoint and the edges Φ(e) for
e ∈ E(F ) are pairwise distinct; and
• for {u, v} ∈ E(F ), Φ({u, v}) has one endpoint in V (Φ(u)) and the other in
V (Φ(v)).

ψ
χ=1
χ=1

χ=0

SF

SF∗

Figure 3: Example of a rooted packing (left) and a potential model matching with it
(right).
See Figure 3 for a schematic illustration of the above definition. The intended meaning of a rooted packing (A, SF∗ , SF , ψ, χ) on a separator B is as follows. The packing A
represents the intersection of the connected components of the potential model with B.
The subsets SF∗ , SF ⊆ V (F ) and the function χ indicate that we are looking in the graph
G for a potential model of F [SF∗ ] containing the edges between vertices in SF given by
the function χ. Namely, the function χ captures which edges of F [SF∗ ] have been realized so far in the processed graph. Since we allow the vertex-models intersecting B
to be disconnected, we need to keep track of their connected components. The subset
SF ⊆ SF∗ tells us which vertex-models intersect B (in other words, SF is the boundary
of F [SF∗ ]), and the function ψ associates the sets in A with the vertices in SF . We can
think of ψ as a coloring that colors the subsets in A with colors given by the vertices in
SF . Note that several subsets in A can have the same color u ∈ SF , which means that
18

the vertex-model of u in G is not connected yet, but it may get connected in further
steps of the dynamic programming. Again, see [1] for the details.
It is proved in [1] that rooted packings allow to carry out dynamic programming in
order to determine whether an input graph G contains a graph F as a minor. It is easy
to see that the number of distinct rooted packings at a separator B is upper-bounded
2
by f (t, F ) := 2t log t · rt · 2r , where t > |B|. In particular, this proves that when G is the
class of graphs excluding a fixed graph H on h vertices as a minor, then the index of the
2
equivalence relation ∼G,t is bounded by 2t log t · ht · 2h .

The encodings generator C EFP . Let G ∈ Bt with boundary ∂(G) labeled with Λ(G).
The function C EFP maps Λ(G) to a set C EFP (Λ(G)) of encodings. Each R ∈ C EFP (Λ(G))
is a set of at most |Λ(G)| rooted packings {(Ai , SF∗ i , SFi , ψi , χi ) | Fi ∈ F}, where each
such rooted packing encodes a potential model of a minor Fi ∈ F (multiple models of
the same graph are allowed).

The language LEFP . For a packing of models S, we say that (G, S, R) belongs to the
language LEFP (or that S is a packing of models satisfying R) if there is a packing of
S
potential models matching with the rooted packings of R in G \ Φ∈S Φ(F ).
Note that we allow the entirely realized models of S to intersect ∂(G) arbitrarily,
but they must not intersect potential models imposed by R.
As mentioned in the introduction, the natural definition of the maximization function
E
does not provide a confined encoder, hence we need to use the relevant function f¯g FP .
In order to define this function we note that, given a separator B and a subgraph GB ,
a (partial) solution naturally induces an encoding RB ∈ C EFP (Λ(GB )), where the rooted
packings correspond to the intersection of models with B.
Formally, let G be a t-boundaried graph with boundary A and let S be a partial
solution satisfying some RA ∈ C EFP (Λ(G)). Let also P be the set of potential models
matching with the rooted packings in RA . Given a separator B in G, we define the
induced encoding RB = {(Ai , SF∗ i , SFi , ψi , χi ) | Φi ∈ S ∪ P} ∈ C EFP (Λ(GB )) such that for
each (potential) model Φi ∈ S ∪ P of Fi ∈ F intersecting B,
• Ai contains elements of the form B ∩ C, where C is a connected component of the
graph induced by V (Φi (v)) ∩ V (GB ), with v ∈ V (Fi );
• ψi maps each element of Ai to its corresponding vertex in Fi ; and
• SF∗ i , SFi , correspond to the vertices of Fi whose vertex models intersect GB and B,
respectively.
Clearly, the set of models of S entirely realized in GB is a partial solution satisfying
RB .
Provided with a formal definition of an induced encoding, and following the description given in Section 4, we can state the definition of an irrelevant encoding for our
problem. Let G ∈ Bt with boundary A and let RA be an encoding. An encoding RA is
19

E
irrelevant for f¯g FP if there exists a certificate S such that (G, S, RA ) ∈ LEFP and |S| =
f EFP (G, RA ), and a separator B ⊆ V (G) with |B| 6 t and B 6= A, such that S induces
E
(as defined above) an encoding RB in the graph GB ∈ Bt with f¯g FP (GB , RB ) = −∞.
E
The function f¯g FP . Let G ∈ Bt with boundary A and let g(t) = t. We define the
E
function f¯g FP as


−∞,
if f EFP (G, RA ) + g(t) <



max{f EFP (G, R) : R ∈ C EFP (Λ(G))}
E
f¯g FP (G, RA ) =
(2)
E

or if RA is irrelevant for f¯g FP .


 f EFP (G, R ), otherwise.
A

In the above equation, f EFP is the natural maximization function associated with the
encoder, that is, f EFP (G, R) is the maximal number of (entire) models in G which do
not intersect potential models imposed by R. Formally,
f EFP (G, R) = max{k : ∃S, |S| > k, (G, S, R) ∈ LEFP }.
2

The size of EFP . Recall that f (t, F ) := 2t log t · rt · 2r is the number of rooted packings
for a minor F of size r on a boundary of size t. If we let r := maxF ∈F |V (F )| and J be
P
any set of positive integers such that j∈J j 6 t, by definition of EFP , it holds that
X
X
2
2
2
2j log j · rj · 2r ) 6 (
2t log t · rt ) · 2r 6 t · 2t log t · rt · 2r . (3)
sEFP (t) 6 (
j∈J

j∈J

Note that an encoding can also be seen as the rooted packing of the disjoint union
of at most t minors of F.
Fact 2. Let G ∈ Bt with boundary A, let Φ be a model (resp. a potential model matching
with a rooted packing defined on A) of a graph F in G, let B be a separator of G, and
let GB ∈ Bt be as in Definition 12. Let (A, SF∗ , SF , φ, χ) be the rooted packing induced by
Φ (as defined above). Let G0B ∈ Bt with boundary B and let G0 be the graph obtained by
replacing GB with G0B . If G0B has a potential model Φ0B matching with (A, SF∗ , SF , φ, χ),
then G0 has a model (resp. a potential model) of F .
Proof. Let us build a model (resp. a potential model) Φ0 of F in G0 . For every vertex v
in V (F ) \ SF∗ , we set Φ0 (v) = Φ(v). For every vertex v in SF∗ \ SF , we set Φ0 (v) = Φ0B (v).
For every vertex v in SF , we set Φ0 (v) = Φ(v)[V (G) \ V (GB )] ⊕ Φ0B (v). As Φ(v) is
connected and the connected components in Φ0B (v) have the same boundaries than the
ones in Φ(v)[V (GB )] (by definition of rooted packing), it follows that Φ0 (v) is connected.
Note that Φ0 (v) do not intersect Φ0 (u), since Φ(v), Φ0B (v) do not intersect Φ0 (u) for any
u ∈ V (F ).
For every edge e in V (F ) × V (F ) \ SF∗ or such that χ(e) = 0 we set Φ0 (e) = Φ(e).
For every edge e in SF∗ × SF∗ \ SF or such that χ(e) = 1 we set Φ0 (e) = Φ0B (e). Since B
is a separator in G, SF is a separator in F and there is no edge in V (F ) \ SF∗ × SF∗ \ SF .
Since Φ, Φ0B are (potential) models, the edges Φ0 (e), e ∈ E(F ) are obviously distinct and
if e = {u, v}, then Φ0 (e) as one endpoint in Φ0 (u) and the other in Φ0 (v).
20

A

A

G0

G0

B

B
G0B
GB

Figure 4: Illustration of a protrusion replacement for F-Packing.
See Figure 4 for an illustration of the scenario described in the statement of Fact 2.
Lemma 6. The encoder EFP is a g-confined cFP-encoder for g(t) = t. Furthermore, if
G is an arbitrary class of graphs, then the equivalence relation ∼∗E ,G,t is DP-friendly.
FP

Proof. Let us first show that the encoder EFP is a cFP-encoder. Indeed, if G is a 0boundaried graph, then C EFP (∅) consists of a single encoding R∅ (an empty set of rooted
packings), and by definition of LEFP , any S such that (G, S, R∅ ) ∈ LEFP is a packing
E
of models. According to Equation (2), there are two possible values for f¯g FP (G, R∅ ):
either f EFP (G, R∅ ), which by definition equals f Π (G), or −∞. Let S be a packing of
E
models of size f Π (G), and assume for contradiction that f¯g FP (G, R∅ ) = −∞. Then, by
a recursive argument we can assume that there is a separator B of size at most t and a
subgraph GB of G as in Definition 12, such that S induces RB and f EFP (GB , RB ) + t <
max{f EFP (G, R) : R ∈ C EFP (I)}. Let M be the set of models entirely realized in GB .
We have |M | = f EFP (GB , RB ), as otherwise S is not maximal. Let MB be the set of
models intersecting B, so we have |MB | 6 t. Finally, let M0 be a packing of models in
GB of size max{f EFP (G, R), R ∈ C EFP (I)}. Clearly, S \ (M ∪ MB ) ∪ M0 is a packing of
models smaller than S (by optimality), that is, |M0 | 6 |M | + t, a contradiction with the
E
E
definition of f¯g FP . Hence f¯g FP (G, R∅ ) = f Π (G).
E
By definition of the function f¯g FP , the encoder EFP is g-confined for g : t 7→ t.
It remains to prove that the equivalence relation ∼∗E ,G,t is DP-friendly for g(t) = t.
FP
Due to Fact 1, it suffices to prove that ∼∗E ,t is DP-friendly. Let G ∈ Bt with boundary
FP
A, let B be any separator of G, and let GB be as in Definition 12. The subgraph GB
can be viewed as a t-boundaried graph with boundary B. We define H ∈ Bt to be the
21

graph induced by V (G) \ (V (GB ) \ B), with boundary B (that is, we forget boundary
A) labeled in the same way than GB . Let G0B ∈ Bt such that GB ∼∗E ,t G0B and let
FP
G0 = H ⊕ G0B , with boundary A. We have to prove that G ∼∗E ,t G0 and ∆EFP ,t (G, G0 ) =
FP
EFP
EFP
0
0
¯
¯
∆E ,t (GB , G ), that is, that fg (G, RA ) = fg (G , RA ) + ∆E ,t (GB , G0 ) for all RA ∈
FP

B

FP

B

C EFP (Λ(G)).
E
Let RA be an encoding defined on A. Assume first that f¯g FP (G, RA ) 6= −∞. Let
E
S = M ∪ MB ∪ MH be a packing of models satisfying RA with size f¯g FP (G, RA ) in G,
with M being the set of models entirely contained in GB , MH the set of models entirely
contained in V (H) \ B, and MB the set of models intersecting B and H. Notice that
M, MB , MH is a partition of S. Let P be the set of potential models matching with the
rooted packings in RA . Let also RB ∈ C EFP (Λ(GB )) be the encoding induced by S ∪ P.
E
Observe that f¯g FP (GB , RB ) 6= −∞, as otherwise, by definition of the relevant funcE
E
tion f¯g FP , we would have that f¯g FP (G, RA ) = −∞. Also, by construction of RB it
E
holds that |M | = f¯g FP (GB , RB ), as otherwise S would not be not maximum. Let
M 0 be a packing of models of F in G0B such that (G0B , M 0 , R) ∈ LEFP and of maxiE
mum cardinality, that is, such that |M 0 | = f¯g FP (G0B , RB ). Consider now the potential
models matching with RB . There are two types of such potential models. The first
ones match with rooted packings defined by the intersection of models in S and B;
we glue them with the potential models defined by H ∩ MB to construct MB0 . The
other ones match with rooted packings defined by the intersection of potential model
in P and B; we glue them with the potential models defined by H ∩ P to construct
E
P 0 . Observe that |MB | = |MB0 |. As GB ∼∗E ,t G0B and f¯g FP (GB , RB ) 6= −∞, we
FP
E
have that |M 0 | = f¯g FP (GB , RB ) + ∆E ,t (GB , G0 ), and therefore |M 0 ∪ M 0 ∪ MH | =
B

FP

B

E
E
f¯g FP (GB , RB ) + ∆EFP ,t (GB , G0B ) + |MB | + |MH | = f¯g FP (G, RA ) + ∆EFP ,t (GB , G0B ).
By definition we have that MH and M 0 are packings of models. The set MB0 contains
vertex-disjoint models by Fact 2. Note that models in MH ∪ M 0 are vertex-disjoint
(because V (H) ∩ V (GB ) = ∅), models in MH ∪ MB0 are vertex-disjoint (because the ones
in MH ∪ MB are vertex-disjoint), and models in M 0 ∪ MB0 are vertex-disjoint (because
M 0 satisfies RB ). Hence MH ∪ M 0 ∪ MB0 is a packing of models.
It remains to prove that MH ∪ M 0 ∪ MB0 satisfies RA . The set P 0 contains vertexdisjoint potential models by Fact 2. Models in P 0 ∪ M 0 are vertex-disjoint, as MB0
satisfies RB . Models in P 0 ∪ MB0 are vertex-disjoint by definition of RB . Finally, models
in P 0 ∪ MH are vertex-disjoint since S satisfies RA .
E
It follows that G0 has a packing of models satisfying RA of size f¯g FP (G, RA ) +
∆EFP ,t (GB , G0B ), that is, G ∼∗E ,t G0 and ∆EFP ,t (G, G0 ) = ∆EFP ,t (GB , G0B ).
FP
E
E
Assume now that f¯g FP (G, RA ) = −∞. If f¯g FP (G0 , RA ) 6= −∞, then applying the
E
same arguments as above we would have that f¯g FP (G, RA ) 6= −∞, a contradiction.

22

5.3

A linear kernel for F-Packing

We are now ready to provide a linear kernel for Connected-Planar-F-Packing.
Theorem 5. Let F be a finite family of connected graphs containing at least one planar
graph on r vertices, let H be an h-vertex graph, and let G be the class of H-minor-free
graphs. Then cpFPG admits a constructive linear kernel of size at most f (r, h)·k, where
f is an explicit function depending only on r and h, defined in Equation (4).
Proof. By Lemma 5, given an instance (G, k) we can either conclude that (G, k) is
a Yes-instance of cpFPG , or build in linear time an ((αH · t) · k 0 , 2t + h)-protrusion
decomposition of G, where αH , t, k 0 are defined in the proof of Lemma 5.
We now consider the encoder EFP defined in Subsection 5.2. By Lemma 6, EFP is a
g-confined cpFPG -encoder and ∼∗E ,G,t is DP-friendly, where g(t) = t and G is the class
FP
of H-minor-free graphs. An upper bound on sEFP (t) is given in Equation (3). Therefore,
we are in position to apply Corollary 1 and obtain a linear kernel for cpFPG of size at
most
(αH · t) · (b (EFP , g, t, G) + 1) · k 0 , where
(4)
• b (EFP , g, t, G) is the function defined in Lemma 3;
• t is the bound on the treewidth provided by Corollary 2;
• k 0 is the parameter of F-Deletion provided by Theorem 3; and
• αH is the constant provided by Theorem 2.
By using the recent results of Chekuri and Chuzhoy [9], it can be shown that the
factor αH = O(h2 2O(h log h) ) in Theorem 3 can be replaced with hO(1) . However, in
this case this would not directly translate into an improvement of the size of the kernel
given in Equation (4), as the term hO(1) would be dominated by the term fm (h) =
2
2O(h log h) .

6

Application to `-F-Packing

We now consider the scattered version of the packing problem. Given a finite set of
graphs F and a positive integer `, the `-F-Packing problem is defined as follows.
`-F-Packing
Instance:
Parameter:
Question:

A graph G and a non-negative integer k.
The integer k.
Does G have k subgraphs G1 , . . . , Gk pairwise at distance at
least `, each containing some graph from F as a minor?

23

We again consider the version of the problem where all the graphs in F are connected
and at least one is planar, called Connected-Planar-`-F-Packing (cp`FP).
We obtain a linear kernel for Connected-Planar `-F-Packing on the family of
graphs excluding a fixed apex graph H as a minor. We use again the notions of model,
packing of models, and rooted packing.

6.1

A protrusion decomposition for an instance of `-F-Packing

In order to obtain a linear protrusion decomposition for `-F-Packing, a natural idea
could be to prove an Erdős-Pósa property at distance `, generalizing the approach for
F-Packing described in Section 5. Unfortunately, the best known Erdős-Pósa relation
between a maximum `-F-packing and a minimum `-F-deletion set is not linear. Indeed,
by following and extending the ideas of Giannopoulou [23, Theorem
√ 8.7 in Section 8.4] for
the special case of cycles, it is possible to derive a bound of O(k k), which is superlinear,
and therefore not enough for our purposes. Proving a linear bound for this Erdős-Pósa
relation, or finding a counterexample, is an exciting topic for further research.
We will use another trick to obtain the decomposition: we will (artificially) consider
the `-F-Packing problem as a vertex-certifiable problem. Hence we propose the formulation described below, which is clearly equivalent to the previous one. Using such
a formulation, a natural question is whether the `-F-Packing problem can fit into the
framework for vertex-certifiable problems [22]. However, finding an appropriate encoder
for this formulation does not seem an easy task, and it is more convenient to describe
the encoder for `-F-Packing using the new framework designed for packing problems.
`-F-Packing
Instance:
Parameter:
Question:

A graph G and a non-negative integer k.
The integer k.
Does G have a set {v1 , . . . , vk } of k vertices such that every vi
belongs to a subgraph Gi of G with G1 , . . . , Gk pairwise at
distance at least ` and each containing some graph from F
as a minor?

With such a formulation, we are in position to use some powerful results from Bidimensionality theory. It is not so difficult to see that the `-F-Packing problem is
contraction-bidimensional [20]. Then we can use Theorem 4 and obtain the following corollary. Again, the bound on the treewidth is derived from the proof of Theorem
4 in [20].
Corollary 3. Let F be a finite set of graphs containing at least one r-vertex planar graph
F , let H be an h-vertex apex graph, and let G be the class of H-minor-free graphs. If
(G, k) ∈ p`FPG , then there exists a set X ⊆ V (G) such that |X| = k and tw(G − X) =
3 · f (h)3 ). Moreover, given an instance (G, k) with |V (G)| = n, there is
O((2r + `)3/2 · τH
c
an algorithm running in time O(n3 ) that either finds such a set X or correctly reports
24

that (G, k) ∈
/ p`FPG .
We are now able to construct a linear protrusion decomposition.
Lemma 7. Let F be a finite set of graphs containing at least one r-vertex planar graph
F , let H be an h-vertex apex graph, and let G be the class of H-minor-free graphs. Let
(G, k) be an instance of Connected Planar-`-F-Packing. If (G, k) ∈ cp`FPG , then
we can construct in polynomial time a linear protrusion decomposition of G.
Proof. Given an instance (G, k) of cp`FPG , we run the algorithm given by Corollary 3.
If the algorithm is not able to find a treewidth-modulator X of size |X| = k, then we can
conclude that (G, k) ∈
/ cp`FPG . Otherwise, we use the set X as input to the algorithm
given by Theorem 2, which outputs in linear time an ((αH · t) · k, 2t + h)-protrusion
decomposition of G, where
3 · f (h)3 ) is provided by Corollary 3; and
• t = O((r + `)3/2 · τH
c

• αH = O(h2 2O(h log h) ) is the constant provided by Theorem 2.

3 · f (h)3 · k, O((r + `)3/2 · τ 3 · f (h)3 ) -proThis is an h2 · 2O(h log h) · (r + `)3/2 · τH
c
c
H
trusion decomposition of G.

6.2

An encoder for `-F-Packing

Our encoder E`FP for `-F-Packing is a combination of the encoder for F-Packing and
the one for `-Scattered Set that we defined in [22].
The encodings generator C E`FP . Let G ∈ Bt with boundary ∂(G) labeled with Λ(G).
The function C E`FP maps Λ(G) to a set C E`FP (Λ(G)) of encodings. Each R ∈ C E`FP (Λ(G))
is a pair (RP , RS ), where
• RP is a set of at most |Λ(G)| rooted packings {(Ai , SF∗ i , SFi , φi , χi ) | i ∈ Λ(G), Fi ∈
F}, where each such rooted packing encodes a potential model of a minor Fi ∈ F
(that is, RP is an encoding of F-Packing); and
• RS maps label j ∈ Λ(G) to an |Λ(G)|-tuple (d, di , i ∈ Λ(G), i 6= j) ∈ [0, ` + 1]|Λ(G)|
(that is, RS is an encoding of `-Scattered Set), for simplicity, since each label
in Λ(G) is uniquely associated with a vertex in ∂(G), we denote by R(v) the vector
assigned by RS to label λ(v).
The language LE`FP . For a packing of models S, we say that (G, S, R) belongs to the
language LE`FP (or that S is a packing of models satisfying R) if
• the models are pairwise at distance at least `, that is, for each Φ1 , Φ2 ∈ S models
of F1 , F2 ∈ F, respectively, dG (V (Φ1 (F1 )), V (Φ2 (F2 ))) > `;
• there is a packing of potential models matching with the rooted packings of RP
S
pairwise at distance at least ` and at distance at least ` from Φ∈S Φ(F ); and
25

• for any vertex v ∈ ∂(G), if (d, di ) = R(v) then dG (v, S ∪ P) > d, and dG (v, w) >
dλ(w) , for any w ∈ ∂(G).
E

Similarly to F-Packing, we need the relevant version of the function f¯g `FP . Let G ∈
Bt with boundary A and let S be a partial solution satisfying some RA ∈ C E`FP (Λ(G)).
Let also P be the set of potential models matching with the rooted packings in RA .
Given a separator B in G, and GB as in Definition 12, we define the induced encoding
RB = (RP , RS ) as follows:
• RP is defined by the intersection of B with models in S ∪ P, (as for F-Packing);
and
• RS maps each v ∈ B to R(v) = (dGB (v, S ∪ P), dGB (v, w), w ∈ B).
The set of models of S entirely realized in GB is a partial solution satisfying RB .
The definition of an irrelevant encoding is as described in Section 4.
E
E
The function f¯g `FP . Let G ∈ Bt with boundary A and let g(t) = 2t. We define f¯g `FP
as

E
f¯g `FP (G, RA ) =











if f E`FP (G, RA ) + 2t <
max{f E`FP (G, R) : R ∈ C E`FP (Λ(G))},
E
or if RA is irrelevant for f¯g `FP .
f E`FP (G, RA ), otherwise.
−∞,

(5)

In the above equation, f E`FP is the natural optimization function defined as
f E`FP (G, R) = max{k : ∃S, |S| > k, (G, S, R) ∈ LE`FP }.

(6)

Size of E`FP . Since C E`FP (I) = C EFP × ([0, ` + 1]t )t , it holds that
2

sE`FP (t) 6 sĒFP (t) × (` + 2)t .

(7)

Lemma 8. The encoder E`FP is a g-confined c`FP-encoder for g(t) = 2t. Furthermore,
if G is an arbitrary class of graphs, then the equivalence relation ∼∗E ,G,t is DP-friendly.
`FP

Proof. We first prove that E`FP is a c`FP-encoder. Obviously, {(G, S) : (G, S, R∅ ) ∈
LE`FP , R∅ ∈ C E`FP (∅)} = LΠ . As in the proof of Lemma 6, in order to show that
E
f E`FP (G, R∅ ) 6= −∞ we prove that the value computed by f¯g `FP has not been truncated.
Let G, GB and S, M, MH , MB , M0 as in proof of Lemma 6, and let M0∗ = M0 \ {Φ(F ) :
∗ = M \ {Φ(F ) : Φ(F ) ∩ N
Φ(F ) ∩ Nr/2 (B) 6= ∅, F ∈ F} and MH
H
r/2 (B) 6= ∅, F ∈ F}.
∗
∗
M0 ∪ MH is a scattered packing of size at least |S| − 2t.
E
The encoder E`FP is g-confined for g : t 7→ 2t by definition of f¯g `FP .
Following the proof of Lemma 6 again, let G, G0 ∈ Bt with boundary A and let
E
E
GB , G0B , H ∈ Bt with boundary B. We have to prove that f¯g `FP (G, RA ) = f¯g `FP (G0 , RA )+
∆E`FP ,t (GB , G0B ) for every RA ∈ C E`FP (Λ(G)).
26

E
Let RA be an encoding defined on A. Assume that f¯g `FP (G, RA ) 6= −∞. Let S =
E
M ∪ MB ∪ MH be a packing of models satisfying RA with size f¯g `FP (G, RA ) in G, with
M, MB , MH as in the proof of Lemma 6. Let also P be the set of potential models
matching with RA and let RB ∈ C E`FP (Λ(GB )) be the encoding induced by S ∪ P.
E
Observe that, by definition, f¯g `FP (GB , RB ) 6= −∞. Hence there is a packing M 0
in G0B of maximum cardinality and such that (G0B , M 0 , R) ∈ LE`FP . As in the proof of
Lemma 6, we can define MB0 to be the set of models obtained from the potential models
defined by the intersection of models in MB with H, glued to the ones in G0B matching
with RB . We can also define P 0 to be the set of potential models obtained from the
potential models defined by the intersection of models in MB with H, glued to the ones
in G0B matching with RB . As GB ∼∗E ,t G0B and following the argumentation in Lemma
`FP
E
6 we have that |M 0 ∪ M 0 ∪ MH | = f¯g `FP (G, RA ) + ∆E ,t (GB , G0 ).
B

`FP

B

We already have that S 0 = MH ∪ M 0 ∪ MB0 is a packing of models according to the
proof of Lemma 6. It remains to prove that (potential) models in S 0 ∪ P 0 are pairwise
at distance at least `. We follow the proof of [22, Lemma 6]. Let P be a shortest path
between any two models in S 0 ∪ P 0 . We subdivide P into maximal subpaths in G0B
and maximal subpaths in H. Clearly the length of a subpath in H does not change.
Moreover, note that the length of a subpath in G0B with extremities v, w ∈ B is at least
dGB (v, w), by definition of RB . Note also that the length of a subpath in G0B with an
extremity in a model and the other v ∈ B is at least dGB (v, S), also by definition of RB .
Therefore, the distance between any two models is indeed at least `.
E
It follows that G0 has a scattered packing of models satisfying RA of size f¯g `FP (G, RA )+
∆E`FP ,t (GB , G0B ), that is, G ∼∗E ,t G0 and ∆E`FP ,t (G, G0 ) = ∆E`FP ,t (GB , G0B ). The case
`FP
E
where f¯g `FP (G, RA ) = −∞ is easily handled as in Lemma 6.

6.3

A linear kernel for `-F-Packing

We are now ready to provide a linear kernel for Connected-Planar-`-F-Packing.
Theorem 6. Let F be a finite family of connected graphs containing at least one planar
graph on r vertices, let H be an h-vertex apex graph, and let G be the class of H-minorfree graphs. Then cp`FPG admits a constructive linear kernel of size at most f (r, h, `)·k,
where f is an explicit function depending only on r, h, and `, defined in Equation (8).
Proof. By Lemma 7, given an instance (G, k) we can either report that (G, k) is a Yesinstance of cp`FPG , or build in linear time an ((αH ·t)·k, 2t+h)-protrusion decomposition
of G, where αH and t are defined in the proof of Lemma 7.
We now consider the encoder E`FP defined in Subsection 6.2. By Lemma 8, E`FP
is a g-confined cp`FPG -encoder and ∼∗E ,G,t is DP-friendly, where g(t) = 2t and G is
`FP
the class of H-minor-free graphs. An upper bound on sE`FP (t) is given in Equation (7).
Therefore, we are in position to apply Corollary 1 and obtain a linear kernel for cp`FPG
of size at most
(αH · t) · (b (E`FP , g, t, G) + 1) · k 0 , where
(8)
27

• b (E`FP , g, t, G) is the function defined in Lemma 3;
• t is the bound on the treewidth provided by Corollary 3; and
• αH is the constant provided by Theorem 2.

7

Application to F-Packing with `-Membership

Now we consider a generalization of the F-Packing problem that allows models to
be close to each other (conversely to `-F-Packing, which asks for scattered models).
That is, we consider the version for minors of the F-Subgraph-Packing with `Membership defined in [16]. Let F be a finite set of graphs. For every integer ` > 1,
we define the F-Packing with `-Membership problem as follows.
F-Packing with `-Membership
Instance: A graph G and a non-negative integer k.
Parameter: The integer k.
Question: Does G have k subgraphs G1 , . . . , Gk such that
each subgraph contains some graph from F as a minor,
and each vertex of G belongs to at most ` subgraphs?
We again consider the version of the problem where all the graphs in F are connected and at least one is planar, called Connected-Planar-F-Packing with `Membership (cpFP`M).
We obtain a linear kernel for Connected-Planar-F-Packing with `-Membership
on the family of graphs excluding a fixed graph H as a minor. We use again the notions
of model, packing of models, and rooted packing.
Now, for an arbitrary graph, a certificate for F-Packing with `-Membership is a
packing of models with `-membership, defined as follows.
Definition 18. Given a set F of minors and a graph G, a packing of models with `membership S is a set of models such that each vertex of G belongs to at most ` models,
that is, to at most ` subgraphs Φ(F ) for Φ ∈ S, F ∈ F.
Note that the above definition is equivalent to saying that each vertex of G belongs
to at most ` vertex-models, since vertex-models of a model are vertex-disjoint.

7.1

A protrusion decomposition for an instance of F-Packing with `Membership

In order to find a linear protrusion decomposition, we use again the Erdős-Pósa property,
as we did in Subsection 5.1. The construction of a linear protrusion decomposition
becomes straightforward from the fact that a packing of models is in particular a packing
of models with `-membership for every integer ` > 1.
28

Lemma 9. Let F be a finite set of graphs containing at least one r-vertex planar graph
F , let H be an h-vertex graph, and let G be the class of H-minor-free graphs. Let (G, k)
be an instance of cpFP`MG . If (G, k) ∈
/ cpFP`MG , then we can construct in polynomial
time a linear protrusion decomposition of G.
Proof. It suffices to note that if S is a packing of models of size k, then it is in particular
a packing of models with `-membership for every integer ` > 1. Hence, if (G, k) ∈
/
cpFPrMG then (G, k) ∈
/ cpFPG and we can apply Lemma 5.

7.2

An encoder for F-Packing with `-Membership

Our encoder EFP`M for F-Packing with `-Membership uses again the notion of rooted
packing, but now we allow the rooted packings to intersect.
The encodings generator C EFP`M . Let G ∈ Bt with boundary ∂(G) labeled with
Λ(G). The function C EFP`M maps Λ(G) to a set C EFP`M (Λ(G)) of encodings. Each R ∈
C EFP`M (Λ(G)) is a set of at most ` · |Λ(G)| rooted packings{(Ai , SF∗ i , SFi , φi , χi ) | Fi ∈ F},
where each such rooted packing encodes a potential model of a minor Fi ∈ F (multiple
models of the same graph are allowed).
The language LEFP`M . For a packing of models with `-membership S, we say that
(G, S, R) belongs to the language LEFP`M (or that S is a packing of models with `membership satisfying R) if there is a packing of potential models with `-membership
matching with the rooted packings of R in G \ {u : u ∈ Φ1 (F1 ), . . . , u ∈ Φ` (F` ); Φi ∈
S, Fi ∈ F}, that is, such that each vertex belongs to at most ` models or potential
models.
E
The function f¯g FP`M . Similarly to F-Packing, we need the relevant version of the
E
E
function f¯g FP`M . The function f¯g FP`M is defined exactly as the one for F-Packing in
Section 5 (in particular, the encoding induced by a partial solution is also the set of
rooted packings defined by the intersection of the partial solution and the separator).
The size of EFP`M . Note that the encoder contains at most `t rooted packings on a
boundary of size t. Hence, if we let r := maxF ∈F |V (F )|, and J be any set such that
P
j∈J j 6 `t and ∀j ∈ J, j 6 t, by definition of EFP`M it holds that
2

sEFP`M (t) 6 `t · 2t log t · rt · 2r .

It just remains to prove that the relation ∼∗E
is DP-friendly. Note that in the
FP`M ,G,t
encoder, the only difference with respect to F-Packing is that rooted packings are now
allowed to intersect. Namely, the constraint on the intersection is that each vertex belongs to at most ` models. This constraint can easily be verify locally, so no information
has to be transmitted through the separator. Hence, the proof of the following lemma
is exactly the same as the proof of Lemma 6, and we omit it.
Lemma 10. The encoder EFP`M is a g-confined cFP`M-encoder for g(t) = t. Furthermore, if G is an arbitrary class of graphs, then the equivalence relation ∼∗E
is
FP`M ,G,t
DP-friendly.
29

7.3

A linear kernel for F-Packing with `-Membership

We are now ready to provide a linear kernel for Connected-Planar F-Packing with
`-Membership.
Theorem 7. Let F be a finite family of connected graphs containing at least one planar
graph on r vertices, let H be an h-vertex graph, and let G be the class of H-minor-free
graphs. Then cpFP`M admits a constructive linear kernel of size at most f (r, h, `) · k,
where f is an explicit function depending only on r, h, and `.
The proof of the above theorem is exactly the same as the one of Theorem 6, the
only difference being in the size sEFP`M (t) of the encoder, and hence in the value of
b (EFP`M , g, t, G).

8

Application to F-Subgraph-Packing

In this section we apply our framework to problems where to objective is to pack subgraphs. The F-Subgraph-Packing problem consists in finding vertex-disjoint subgraphs (instead of minors) isomorphic to graphs in a given finite family F. Similarly to F-(Minor)-Packing, we study two more generalizations of the problem,
namely the `-F-Subgraph-Packing, asking for subgraphs at distance ` from each
other, and the F-Subgraph-Packing with `-Membership problem [16] that allows
vertices to belong to at most ` subgraphs. Let F be a finite set of graphs and let
` > 1 be an integer. The F-Subgraph-Packing, the `-F-Subgraph-Packing, and
the F-Subgraph-Packing with `-Membership problems are defined as follows.
F-Subgraph-Packing
Instance: A graph G and a non-negative integer k.
Parameter: The integer k.
Question: Does G have k vertex-disjoint subgraphs
G1 , . . . , Gk , each isomorphic to a graph in F?
`-F-Subgraph-Packing
Instance: A graph G and two non-negative integers k and `.
Parameter: The integer k.
Question: Does G have k subgraphs G1 , . . . , Gk pairwise at distance
at least ` and each isomorphic to a graph in F?

30

F-Subgraph-Packing with `-Membership
Instance: A graph G and two non-negative integers k and `.
Parameter: The integer k.
Question: Does G have k subgraphs G1 , . . . , Gk , each isomorphic to
in F, and a graph such that each vertex of G belongs
to at most ` subgraphs?
Again, for technical reasons, we consider the versions of the above problems where
all the graphs in F are connected, called Connected F-Subgraph-Packing (cFSP),
Connected`-F-Subgraph-Packing (c`FSP),and Connected F-Subgraph-Packing with `-Membership (cFSP`M), respectively. As in Section 5, connectivity is necessary to use the equivalent notion of rooted packings. Furthermore, in this section we
also need connectivity to build the protrusion decomposition, whereas the presence of a
planar graph in F is not mandatory anymore.
Similarly to F-Packing, we establish a relation between instances of F-Subgraph
-Packing (and its variants) and instances of d-Dominating Set for an appropriate
value of d. Therefore we also define this problem. Note that here we do not use any
Erdős-Pósa property to establish this relation.
d-Dominating
Instance:
Parameter:
Question:

Set
A graph G and two non-negative integers k and d.
The integer k.
Is there a set D of vertices in G with size at most k,
such that for every vertex v ∈ V (G), Nd [v] ∩ D 6= ∅?

In this section we obtain a linear kernel for Connected F-Subgraph-Packing, Connected `-F-Subgraph-Packing, and F-Subgraph-Packing with `-Membership
on the families of graphs excluding respectively a fixed graph, a fixed apex graph, and
a fixed graph, as a minor.
For these three problems, the structure of a solution will be respectively a packing
of subgraph models, a packing of subgraph models, and a packing of subgraph models with
`-membership. In order to define a packing of subgraph models, we need the definition
of a subgraph model of F in G, which is basically an isomorphism from a graph F to a
subgraph of G.
Definition 19. A subgraph model of a graph F in a graph G is a mapping Φ, that
assigns to every vertex v ∈ V (F ) a vertex Φ(v) ∈ v(G), such that
• the vertices Φ(v) for v ∈ V (F ) are distinct; and
• if {u, v} ∈ E(F ), then {Φ(u), Φ(v)} ∈ E(G).
We denote by Φ(F ) the subgraph of G with vertex set {Φ(v) : v ∈ V (F )} and edge
set {{Φ(u), Φ(v)} : {u, v} ∈ E(F )}, which is obviously isomorphic to F .
31

Definition 20. Let F be a set of subgraphs and let G be a graph. A packing of subgraph
models S is a set of vertex-disjoint subgraph models, that is, the graphs Φ(F ) for Φ ∈
S, F ∈ F are vertex-disjoint. A packing of subgraph models with `-membership S is
a set of subgraph models such that every vertex v ∈ V (G) is the image of at most `
mappings Φ ∈ S.

8.1

A protrusion decomposition for an instance of F-Subgraph-Packing

In order to find a linear protrusion decomposition, we first need a preprocessing reduction rule. This rule, which has also been used in previous work [5, 20], enables us to
establish a relation between instances of F-Subgraph-Packing (and its variants) and
d-Dominating Set. Then we will be able to apply Theorem 4 on d-Dominating Set
to find a linear treewidth-modulator that allows to construct the decomposition.
Rule 1. Let v be a vertex of G that does not belong to any subgraph of G isomorphic to
a graph in F. Then remove v from G.
Note that Rule 1 can be applied in time O(nr ), where n is the size of G and r is the
maximum size of a graph in F. We call a graph reduced under Rule 1 if the rule cannot
be applied anymore on G.
The next proposition states a relation between an instance of `-F-Subgraph-Packing
and d-Dominating Set. The relation with the two other problems are straightforward,
as explained below.
Proposition 3. Let G be a graph reduced under Rule 1. If (G, k) is a No-instance
of Connected `-F-Subgraph-Packing, then (G, k) is a Yes-instance of (2d + `)Dominating Set, where d is the largest diameter of the graphs in F.
Proof. Let (G, k) be a No-instance of `-F-Subgraph-Packing and let d be the largest
diameter of a graph in F. Let us choose any vertex v ∈ V (G) and remove Nd+` (v) from
G. We repeat this operation until there is no subgraph model of F in G. We call D the
set of removed vertices. As (G, k) is a No-instance of F-Subgraph-Packing, |D| 6 k
and as G is reduced under Rule 1 all vertices in V (G) \ Nd+` (D) belong to a (connected)
subgraph model (which intersects Nd+` (D)), hence all vertices in V (G) \ Nd+` (D) are
at distance at most 2d + ` from D. Therefore (G, k) is a Yes-instance of (2d + `)Dominating Set.
Note that if (G, k) is a No-instance of F-Subgraph-Packing with `-Membership
then it is a No-instance of F-Subgraph-Packing (that is, of 1-F-Subgraph-Packing)
and then it is a No-instance of `-F-Subgraph-Packing for every integer ` > 1. According to Proposition 3, it follows that (G, k) is a Yes-instance of (2d+1)-Dominating
Set.
We now apply Theorem 4 in order to find a treewidth-modulator for a Yes-instance of
(2d + 1)-Dominating Set. We now use the following corollary of Theorem 4.

32

Corollary 4. Let F be a finite set of connected graphs, let H be an h-vertex apex graph,
and let G be the class of H-minor-free graphs. If (G, k)
G , then there exists a set
√ ∈ d-DS
3 · f (h)3 ). Moreover, given
X ⊆ V (G) such that |X| = k and tw(G − X) = O(d d · τH
c
an instance (G, k) with |V (G)| = n, there is an algorithm running in time O(n3 ) that
either finds such a set X or correctly reports that (G, k) ∈
/ d-DSG .
We are now able to construct a linear protrusion decomposition.
Lemma 11. Let F be a finite set of connected graphs, let H be an h-vertex apex
graph, and let G be the class of H-minor-free graphs. Let (G, k) be an instance of
Connected-`-F-Subgraph-Packing (or of Connected-F-Subgraph-Packing, or
of Connected-F-Subgraph-Packing with `-Membership). If (G, k) ∈
/ cFSPG ,
then we can construct in polynomial time a linear protrusion decomposition of G.
Proof. Given an instance (G, k) of cFSPG , we run the algorithm given by Corollary 4
for the Connected (2d + `)-Dominating Set problem, where d is the largest diameter
of the graphs in F. If the algorithm is not able to find a treewidth-modulator X of
size |X| = k, then by Proposition 3 we can conclude that (G, k) ∈ c`FSPG (resp.
(G, k) ∈ cFSPG and (G, k) ∈ cFSP`MG ). Otherwise, we use the set X as input to
the algorithm given by Theorem 2, which outputs in linear time an ((αH · t) · k, 2t + h)protrusion decomposition of G, where
3 · f (h)3 ) is provided by Corollary 4; and
• t = O((2d + `)3/2 · τH
c

• αH = O(h2 2O(h log h) ) is the constant provided by Theorem 2.

3 · f (h)3 · k , O((2d + `)3/2 · τ 3 · f (h)3 ) -proThis is an h2 2O(h log h) · (2d + `)3/2 · τH
c
m
H
trusion decomposition of G.

8.2

An encoder for F-Subgraph-Packing

Our encoder EFSP for F-Subgraph-Packing uses a simplified version of rooted packings.
Definition 21. Let F be a connected graph and let G be a boundaried graph with boundary B. A rooted set of B is a quadruple (A, SF∗ , SF , ψ), where
• SF ⊆ SF∗ are both subsets of V (F );
• A is a non-empty subset of B; and
• ψ : A → SF is a bijective mapping assigning vertices of SF to the vertices in A.
We also define a potential subgraph model of F in G matching with (A, SF∗ , SF , ψ)
as a partial mapping Φ, that assigns to every vertex v ∈ SF a vertex Φ(v) ∈ A such
that ψ(Φ(v)) = v, and to every vertex v ∈ SF∗ a vertex Φ(v) ∈ V (G) such that for all
u, v ∈ SF∗ if {u, v} ∈ E(F ) then, {Φ(u), Φ(v)} ∈ E(G). Moreover, for every v ∈ SF∗ \ SF ,
it holds that Φ(v) ∈ V (G) \ B.
33

Intuitively, the rooted set is a simplification of the rooted packing defined in Section
5. The collection A of subsets of B is replaced with a subset A of B (since now the image
of a vertex v ∈ V (F ) is a vertex of G). The sets SF∗ , SF still describe the subgraph of F
which is realized in G and its vertices that lie in B. The function ψ plays the same role
as in rooted packings: it can be viewed as the inverse of the potential subgraph model
Φ restricted to B. Note that we do not need the function χ anymore because the edges
cannot appear later (because now the image of a vertex v ∈ V (F ) is a vertex, and we
are dealing with a tree decomposition).
The number of distinct rooted sets at a separator B is upper-bounded by f (t, F ) :=
t
2 · rt · 22r , where t > |B| and r = |V (F )|.
Here, we only describe the encoder for F-Subgraph-Packing. Similarly to Section 6, the encoder for `-F-Subgraph-Packing is obtained by a combination of the
encoder for F-Subgraph-Packing and the one for `-Scattered Set. As in Section 7,
the encoder for F-Subgraph-Packing with `-Membership is obtained by allowing
intersections in the rooted set.
The encodings generator C EFSP . Let G ∈ Bt with boundary ∂(G) labeled with Λ(G).
The function C EFSP maps Λ(G) to a set C EFSP (Λ(G)) of encodings. Each R ∈ C EFSP (Λ(G))
is a set of at most |Λ(G)| rooted sets {(Ai , SF∗ i , SFi , ψi ) : Fi ∈ F}, where each such rooted
set encodes a potential subgraph model of Fi ∈ F (multiple subgraphs models of the
same graph are allowed), and where the sets Ai are pairwise disjoint.
The language LEFSP . For a packing of subgraph models S, we say that (G, S, R)
belongs to the language LEFSP (or that S is a packing of models satisfying R) if there is
a packing of vertex-disjoint potential subgraph models matching with the rooted sets of
S
R in G \ Φ∈S Φ(F ).
Note that we allow the entirely realized subgraph models of S to intersect ∂(G) arbitrarily, but they must not intersect potential subgraph models imposed by R.
E
As in the previous sections, we need to use the relevant function f¯g FSP . To this aim,
we need to remark that, given a separator B and a subgraph GB , a (partial) solution
naturally induces an encoding RB ∈ C EFSP (Λ(GB )) where the rooted sets correspond to
the intersection of models with B.
Formally, let G be a t-boundaried graph with boundary A and let S be a partial
solution satisfying some RA ∈ C EFSP (Λ(G)). Let also P be the set of potential subgraph
models matching with the rooted set in RA . Given a separator B in G, we define the
induced encoding RB = {(Ai , SF∗ i , SFi , ψi ) : Φi ∈ S ∪ P} ∈ C EFSP (Λ(GB )) such that for
each (potential) subgraph model Φi ∈ S ∪ P of Fi ∈ F intersecting B,

• Ai contains vertices of Φi (Fi ) in B;
• ψi maps each vertex of Ai to its corresponding vertex in Fi ; and
• SF∗ i and SFi correspond to the vertices of Fi whose images by Φ belong to GB and
B, respectively.
34

Clearly, the set of models of S entirely realized in GB is a partial solution satisfying RB .
The definition of an irrelevant encoding is the same as in Section 4.
E
E
The function f¯g FSP . Let G ∈ Bt with boundary A. We define the function f¯g FSP as
E
f¯g FSP (G, RA ) =











if f EFSP (G, RA ) + t <
max{f EFSP (G, R) : R ∈ C EFSP (Λ(G))}
E
or if RA is irrelevant for f¯g FSP .
f EFSP (G, R), otherwise.

−∞,

In the above equation, f EFSP is the natural maximization function, that is f EFSP (G, R)
is the maximal number of (entirely realized) subgraph models in G which do not intersect
potential subgraph models imposed by R. Formally,
f EFSP (G, R) = max{k : ∃S, |S| > k, (G, S, R) ∈ LEFSP }.
The size of EFSP . Recall that f (t, F ) := 2t · rt · 22r is the number of rooted sets for a
subgraph F of size r on a boundary of size t. Our encoder contains at most t vertexdisjoint rooted sets, for subgraphs of size at most r := maxF ∈F |V (F )| and such that the
sum of their boundary size is at most t. Hence we can bound the size of the encoder as
X

sEFSP (t) 6
2j · rj · 22r 6 t · 2t · rt · 22r .
j∈J

Note that the encoder for `-F-Subgraph-Packing generates couples of encodings
for F-Subgraph-Packing and `-Scattered Set, and therefore the size of the encoder
can be bounded as
2
sE`FSP (t) 6 sEFSP (t) · (` + 2)t .
Finally, note that the encoder for F-Subgraph-Packing with `-Membership contains at most `t rooted sets on a boundary of size t, and thus the size of the encoder can
be bounded as
sEFSP `M (t) 6 `t · 2t · rt · 22r .
Similarly to Fact 2, the following fact claims that rooted sets allow us to glue and
unglue boundaried graphs, preserving the existence of subgraphs. We omit the proof as
it is very similar to the one of Fact 2.
Fact 3. Let G ∈ Bt with boundary A, let Φ be a subgraph model (resp. a potential
subgraph model matching with a rooted set defined on A) of a graph F in G, let B be
a separator of G, and let GB ∈ Bt be as in Definition 12. Let (A, SF∗ , SF , ψ) be the
rooted set induced by Φ (as defined above). Let G0B ∈ Bt with boundary B and let G0 be
the graph obtained by replacing GB with G0B . If G0B has a potential subgraph model Φ0B
matching with (A, SF∗ , SF , ψ), then G0 has a subgraph model (resp. a potential subgraph
model) of F .

35

We now have to prove that the encoders EFSP , E`FSP , EFSP `M are confined and DPfriendly. The proofs are very similar to the proof of Lemma 6; the proofs for E`FSP and
EFSP `M have to be adapted following Sections 6 and 7, respectively. This seems natural as
the encoder EFSP is defined with rooted sets, which are simplifications of rooted packings.
Lemma 12. The encoders EFSP , E`FSP , and EFSP `M are g-confined for g(t) = t, g(t) = 2t,
and g(t) = t, respectively. They are respectively a cFSP-encoder, a c`FSP-encoder,
and a cFSP`M -encoder. Furthermore, if G is an arbitrary class of graphs, then the
equivalence relations ∼∗E ,G,t , ∼∗E`FSP ,G,t , and ∼∗EFSP `M ,G,t are DP-friendly.
FSP

8.3

A linear kernel for F-Subgraph-Packing

We are now ready to provide a linear kernel for Connected F-Subgraph-Packing,
Connected `-F-Subgraph-Packing, and Connected F-Subgraph-Packing with
`-membership.
Theorem 8. Let F be a finite family of connected graphs with diameter at most d, let H
be an h-vertex graph, and let G be the class of H-minor-free graphs. Then Connected
F-Subgraph-Packing, Connected `-F-Subgraph-Packing, and Connected FSubgraph Packing with `-Membership admit constructive kernels of size O(k),
where the constant hidden in the “O” notation depends on h, d, and `.
The proof is similar to the ones in the previous sections. Using the protrusion
decomposition given by Lemma 11 and the encoders described in Section 8.2, we have
all the material to apply Corollary 1. The size of the kernel differs from the previous
sections due to the size of the encoders and due to the bound on the treewidth of
protrusions given by Lemma 11.
To conclude, we would like to mention that Romero and López-Ortiz [32] introduced another problem allowing intersection of subgraph models, called F-(Subgraph)Packing with `-Overlap. In this problem, also studied in [16, 33], a subgraph model
can intersect any number of other models, but they are allowed to pairwise intersect on
at most ` vertices. It is easier to perform dynamic programming on the membership
version than on the overlap version, since the intersection constraint is local for the
first one (just on vertices) but global for the second one (on pairs of models). However,
we think that it is possible to define an encoder (with all the required properties) for
F-(Subgraph)-Packing with `-Overlaps using rooted sets and vectors of integers
counting the overlaps (similarly to `-F-Subgraph-Packing). This would imply the
existence of a linear kernel for the F-(Subgraph)-Packing with `-Overlap problem
on sparse graphs. We leave it for further research.

9

Conclusions and further research

In this article we generalized the framework introduced in [22] to deal with packingcertifiable problems. Our main result can be seen as a meta-theorem, in the sense that
36

as far a particular problem satisfies the generic conditions stated in Corollary 1, 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 fc defined in Proposition 2, which depends
exclusively on the considered graph class (and not on each particular problem). In order
to find explicit bounds for this function fc , we leave as future work using the lineartime deterministic protrusion replacer recently introduced by Fomin et al. [18], partially
inspired from [22].
Acknowledgement. We would like to thank Archontia C. Giannopoulou for insightful
discussions about the Erdős-Pósa property for scattered planar minors.

References
[1] I. Adler, F. Dorn, F. V. Fomin, I. Sau, and D. M. Thilikos. Faster parameterized
algorithms for minor containment. Theoretical Computer Science, 412(50):7018–
7028, 2011.
[2] J. Alber, M. Fellows, and R. Niedermeier. Polynomial-Time Data Reduction for
Dominating Set. Journal of the ACM, 51(3):363–384, 2004.
[3] A. Atminas, M. Kaminski, and J.-F. Raymond. Scattered packings of cycles. Theoretical Computer Science, 647:33–42, 2016.
[4] H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small
treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996.
[5] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and
D. M. Thilikos. (Meta) Kernelization. In Proc. of the 50th IEEE Symposium on
Foundations of Computer Science (FOCS), pages 629–638. IEEE Computer Society,
2009.
[6] H. L. Bodlaender, S. Thomassé, and A. Yeo. Kernel bounds for disjoint cycles and
disjoint paths. Theoretical Computer Science, 412(35):4570–4578, 2011.
[7] J. R. Büchi. Weak second order arithmetic and finite automata. Zeitschrift für
mathematische Logik und Grundlagen der Mathematik, 6:66–92, 1960.

37

[8] C. Chekuri and J. Chuzhoy. Large-treewidth graph decompositions and applications. In Proc. of the 45th Symposium on the Theory of Computing (STOC), pages
291–300, 2013.
[9] C. Chekuri and J. Chuzhoy. Polynomial bounds for the grid-minor theorem. In
Proc. of the 46th ACM Symposium on the Theory of Computing (STOC), pages
60–69, 2014.
[10] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
[11] M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O.
Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single
exponential time. In Proc. of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 150–159. IEEE Computer Society, 2011.
[12] E. D. Demaine and M. Hajiaghayi. Linearity of grid minors in treewidth with
applications through bidimensionality. Combinatorica, 28(1):19–36, 2008.
[13] R. Diestel. Graph Theory, volume 173. Springer-Verlag, 4th edition, 2010.
[14] P. Erdős and L. Pósa. On independent circuits contained in a graph. Canadian
Journal of Mathematics, 17:347–352, 1965.
[15] M. R. Fellows, J. Guo, C. Komusiewicz, R. Niedermeier, and J. Uhlmann. Graphbased data clustering with overlaps. Discrete Optimization, 8(1):2–17, 2011.
[16] H. Fernau, A. López-Ortiz, and J. Romero. Kernelization algorithms for packing
problems allowing overlaps. In Proc. of the 12th Annual Conference on Theory
and Applications of Models of Computation, (TAMC), volume 9076 of LNCS, pages
415–427, 2015.
[17] F. V. Fomin, P. A. Golovach, and D. M. Thilikos. Contraction obstructions for
treewidth. Journal of Combinatorial Theory, Series B, 101(5):302–314, 2011.
[18] F. V. Fomin, D. Lokshtanov, N. Misra, M. S. Ramanujan, and S. Saurabh. Solving dSAT via Backdoors to Small Treewidth. In Proc. of the 26th ACM-SIAM Symposium
on Discrete Algorithms (SODA), pages 630–641, 2015.
[19] F. V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh. Bidimensionality and EPTAS. In Proc. of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA),
pages 748–759, 2011.
[20] F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. Bidimensionality
and kernels. In Proc. of the 21st ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 503–510, 2010.

38

[21] F. V. Fomin, S. Saurabh, and D. M. Thilikos. Strengthening Erdős-Pósa property
for minor-closed graph classes. Journal of Graph Theory, 66(3):235–240, 2011.
[22] V. Garnero, C. Paul, I. Sau, and D. M. Thilikos. Explicit linear kernels via dynamic
programming. SIAM Journal on Discrete Mathematics, 29(4):1864–1894, 2015.
[23] A. Giannopoulou. Partial Orderings and Algorithms on Graphs. PhD thesis, Department of Mathematics, University of Athens, Greece, 2012.
[24] J. Guo and R. Niedermeier. Linear problem kernels for NP-hard problems on planar
graphs. In Proc. of the 34th International Colloquium on Automata, Languages and
Programming (ICALP), volume 4596 of LNCS, pages 375–386, 2007.
[25] K. Kawarabayashi and Y. Kobayashi. Linear min-max relation between the
treewidth of H-minor-free graphs and its largest grid. In Proc. of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 14
of LIPIcs, pages 278–289, 2012.
[26] E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau, and S. Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM
Transactions on Algorithms, 12(2):21, 2016.
[27] T. Kloks. Treewidth. Computations and Approximations. Springer-Verlag LNCS,
1994.
[28] D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential
time hypothesis. Bulletin of the EATCS, 105:41–72, 2011.
[29] H. Moser. A problem kernelization for graph packing. In Proc. of the 35th International Conference on Current Trends in Theory and Practice of Computer Science
(SOFSEM), volume 5404 of LNCS, pages 401–412, 2009.
[30] N. Robertson and P. D. Seymour. Graph Minors. V. Excluding a Planar Graph.
Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.
[31] N. Robertson and P. D. Seymour. Graph Minors. XIII. The Disjoint Paths Problem.
Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.
[32] J. Romero and A. López-Ortiz. The G-packing with t-overlap problem. In Proc.
of the 8th International Workshop on Algorithms and Computation (WALCOM),
volume 8344 of LNCS, pages 114–124, 2014.
[33] J. Romero and A. López-Ortiz. A parameterized algorithm for packing overlapping
subgraphs. In Proc. of the 9th International Computer Science Symposium in Russia
(CSR), volume 8476 of LNCS, pages 325–336, 2014.

39

A
A.1

Deferred proofs in Section 3
Proof of Lemma 1

Let us first show that the equivalence relation ∼∗E ,t has finite index. Let I ⊆ {1, . . . , t}.
FSP
Since we assume that EFSP is g-confined, we have that for any G ∈ Bt with Λ(G) = I, the
function f EFSP (G, · ) can take at most g(t) + 2 distinct values (g(t) + 1 finite values and
possibly the value −∞). Therefore, it follows that the number of equivalence classes of
E
∼∗E ,t containing all graphs G ∈ Bt with Λ(G) = I is at most (g(t) + 2)|C FSP (I)| . As the
FSP
number of subsets of {1, . . . , t} is 2t , we deduce that the overall number of equivalence
s
(t)
classes of ∼∗E ,t is at most (g(t) + 2) EFSP · 2t . Finally, since the equivalence relation
FSP
∼∗E ,G,t is the Cartesian product of the equivalence relations ∼∗E ,t and ∼G,t , the result
FSP
FSP
follows from the fact that G can be expressed in MSO logic.

A.2

Proof of Fact 1

Let G = G− ⊕ GB and let G0 = G− ⊕ G0B . Assume that G ∼∗E ,t G0 . In order to
FSP
deduce that G ∼∗E ,G,t G0 , it suffices to prove that G ∼G,t G0 . Let H ∈ Bt . We
FSP
need to show that G ⊕ H ∈ G if and only if G0 ⊕ H ∈ G. We have that G ⊕ H =
(GB ⊕ G− ) ⊕ H = GB ⊕ (G− ⊕ H), and similarly for G0 . Since GB ∼G,t G0B , it follows
that G ⊕ H = GB ⊕ (G− ⊕ H) ∈ G if and only if GB ⊕ (G− ⊕ H) = G ⊕ H ∈ G.

A.3

Proof of Lemma 2

Let EFSP = (C EFSP , LEFSP , f EFSP ) be a Π-encoder and let G1 , G2 ∈ Bt such that G1 ∼EFSP ,t
G2 . We need to prove that for any H ∈ Bt and any integer k, (G1 ⊕ H, k) ∈ Π if and
only if (G2 ⊕ H, k + ∆EFSP ,t (G1 , G2 )) ∈ Π.
Suppose that (G1 ⊕ H, k) ∈ Π (by symmetry the same arguments apply starting with
G2 ). Since G1 ⊕ H is a 0-boundaried graph and EFSP is a Π-encoder, we have that
f EFSP (G1 ⊕ H, R∅ ) = f Π (G1 ⊕ H) > k.

(9)

As ∼∗E ,G,t is DP-friendly and G1 ∼∗E ,G,t G2 , it follows that (G1 ⊕H) ∼∗E ,G,t (G2 ⊕H)
FSP
FSP
FSP
and that ∆EFSP ,t (G1 ⊕H, G2 ⊕H) = ∆EFSP ,t (G1 , G2 ). Since G2 ⊕H is also a 0-boundaried
graph, the latter property and Equation (9) imply that
f EFSP (G2 ⊕ H, R∅ ) = f EFSP (G1 ⊕ H, R∅ ) + ∆EFSP ,t (G1 , G2 ) > k + ∆EFSP ,t (G1 , G2 ). (10)
Since EFSP is a Π-encoder, f Π (G2 ⊕ H) = f EFSP (G2 ⊕ H, R∅ ), and from Equation (10) it
follows that (G2 ⊕ H, k + ∆EFSP ,t (G1 , G2 )) ∈ Π.

A.4

Proof of Lemma 3

Let C be an arbitrary equivalence class of ∼EFSP ,G,t , and let G1 , G2 ∈ C. Let us first argue
that C contains some progressive representative. Since ∆EFSP ,t (G1 , G2 ) = f EFSP (G1 , R) −
40

f EFSP (G2 , R) for every encoding R such that f EFSP (G1 , R), f EFSP (G2 , R) 6= −∞, G ∈ C
is progressive if f EFSP (G, R) is minimal in f EFSP (C, R) = {f (G, R) : G ∈ C} for every
encoding R (including those for which the value is −∞). Since f EFSP (C, R) is a subset
of N ∪ {−∞}, it necessarily has a minimal element, hence there is a progressive representative in C (in other words, the order defined by G1 4 G2 if ∆EFSP ,t (G1 , G2 ) 6 0 is
well-founded).
Now let G ∈ G be a progressive representative of C with minimum number of vertices.
We claim that G has size at most 2r(E,g,t,G)+1 · t (we would like to stress that at this stage
we only need to care about the existence of such representative G, and not about how
to compute it). Let (T, X ) be a boundaried nice tree decomposition of G of width at
most t − 1 such that ∂(G) is contained in the root-bag (such a nice tree decomposition
exists by [27]).
We first claim that for any node x of T , the graph Gx is a progressive representative of its equivalence class with respect to ∼EFSP ,G,t , namely C0 . Indeed, assume
for contradiction that Gx is not progressive, and therefore we know that there exists
G0x ∈ C0 such that ∆EFSP ,t (G0x , Gx ) < 0. Let G0 be the graph obtained from G by replacing Gx with G0x . Since ∼∗E ,G,t is DP-friendly, it follows that G ∼EFSP ,G,t G0 and
FSP
that ∆EFSP ,t (G0 , G) = ∆EFSP ,t (G0x , Gx ) < 0, contradicting the fact that G is a progressive
representative of the equivalence class C.
We now claim that for any two nodes x, y ∈ V (T ) lying on a path from the root
to a leaf of T , it holds that Gx EFSP ,G,t Gy . Indeed, assume for contradiction that
there are two nodes x, y ∈ V (T ) lying on a path from the root to a leaf of T such that
Gx ∼EFSP ,G,t Gy . Let C0 be the equivalence class of Gx and Gy with respect to ∼EFSP ,G,t .
By the previous claim, it follows that both Gx and Gy are progressive representatives of
C0 , and therefore it holds that ∆EFSP ,t (Gy , Gx ) = 0. Suppose without loss of generality
that Gy ( Gx (that is, Gy is a strict subgraph of Gx ), and let G0 be the graph obtained from G by replacing Gx with Gy . Again, since ∼∗E ,G,t is DP-friendly, it follows
FSP
that G ∼EFSP ,G,t G0 and that ∆EFSP ,t (G0 , G) = ∆EFSP ,t (Gy , Gx ) = 0. Therefore, G0 is a
progressive representative of C with |V (G0 )| < |V (G)|, contradicting the minimality of
|V (G)|.
Finally, since for any two nodes x, y ∈ V (T ) lying on a path from the root to a leaf of
T we have that Gx EFSP ,G,t Gy , it follows that the height of T is at most the number of
equivalence classes of ∼EFSP ,G,t , which is at most r(EFSP , g, t, G) by Lemma 1. Since T is
a binary tree, we have that |V (T )| 6 2r(E,g,t,G)+1 − 1. Finally, since |V (G)| 6 |V (T )| · t,
it follows that |V (G)| 6 2r(E,g,t,G)+1 · t, as we wanted to prove.

A.5

Proof of Lemma 4

Let EFSP = (C EFSP , LEFSP , f EFSP ) be the given encoder. We start by generating a repository
R containing all the graphs in Ft with at most b + 1 vertices. Such a set of graphs, as
well as a boundaried nice tree decomposition of width at most t − 1 of each of them,
can be clearly generated in time depending only on b and t. By assumption, the size of
41

a smallest progressive representative of any equivalence class of ∼EFSP ,G,t is at most b,
so R contains a progressive representative of any equivalence class of ∼EFSP ,G,t with at
most b vertices. We now partition the graphs in R into equivalence classes of ∼EFSP ,G,t
as follows: for each graph G ∈ R and each encoding R ∈ C EFSP (Λ(G)), as LEFSP and
f EFSP are computable, we can compute the value f EFSP (G, R) in time depending only
on EFSP , g, t, and b. Therefore, for any two graphs G1 , G2 ∈ R, we can decide in time
depending only on EFSP , g, t, b, and G whether G1 ∼EFSP ,G,t G2 , and if this is the case, we
can compute the transposition constant ∆EFSP ,t (G1 , G2 ) within the same running time.
Given a t-protrusion Y on n vertices with boundary ∂(Y ), we first compute a boundaried nice tree decomposition (T, X , r) of Y in time f (t) · n, by using the linear-time
algorithm of Bodlaender [4, 27]. Such a t-protrusion Y equipped with a tree decomposition can be naturally seen as a t-boundaried graph by assigning distinct labels from
{1, . . . , t} to the vertices in the root-bag. We can assume that Λ(Y ) = {1, . . . , t}. Note
that the labels can be transferred to the vertices in all the bags of (T, X , r), by performing a standard shifting procedure when a vertex is introduced or removed from the
nice tree decomposition [5]. Therefore, each node x ∈ V (T ) defines in a natural way
a t-protrusion Yx ⊆ Y with its associated boundaried nice tree decomposition, with all
the boundary vertices contained in the root bag. Let us now proceed to the description
of the replacement algorithm.
We process the bags of (T, X ) in a bottom-up way until we encounter the first node
x in V (T ) such that |V (Yx )| = b + 1 (note that as (T, X ) is a nice tree decomposition,
when processing the bags in a bottom-up way, at most one new vertex is introduced at
every step, and recall that b > t, hence such an x exists). We compute the equivalence
class C of Yx according to ∼EFSP ,G,t ; this corresponds to computing the set of encodings
C EFSP (Λ(Yx )) and the associated values of f EFSP (Yx , ·) that, by definition of an encoder,
can be calculated since f EFSP is a computable function. As |V (Yx )| = b + 1, the graph
Yx is contained in the repository R, so in constant time we can find in R a progressive
representative Yx0 of C with at most b vertices and the corresponding transposition constant ∆EFSP ,t (Yx0 , Yx ) 6 0, (the inequality holds because Yx0 is progressive). Let Z be the
graph obtained from Y by replacing Yx with Yx0 , so we have that |V (Y )| < |V (Z)| (note
that this replacement operation directly yields a boundaried nice tree decomposition of
width at most t − 1 of Z). Since ∼∗E ,G,t is DP-friendly, it follows that Y ∼EFSP ,G,t Z
FSP
and that ∆EFSP ,t (Z, Y ) = ∆EFSP ,t (Yx0 , Yx ) 6 0.
We recursively apply this replacement procedure on the resulting graph until we eventually obtain a t-protrusion Y 0 with at most b vertices such that Y ∼EFSP ,G,t Y 0 . The
corresponding transposition constant ∆EFSP ,t (Y 0 , Y ) can be easily computed by summing up all the transposition constants given by each of the performed replacements.
Since each of these replacements introduces a progressive representative, we have that
∆EFSP ,t (Y 0 , Y ) 6 0. As we can assume that the total number of nodes in a nice tree
decomposition of Y is O(n) [27, Lemma 13.1.2], the overall running time of the algorithm is O(n) (the constant hidden in the “O” notation depends indeed exclusively on
EFSP , g, b, G, and t).
42

A.6

Proof of Theorem 1

By Lemma 1, the number of equivalence classes of the equivalence relation ∼EFSP ,G,t is
finite and by Lemma 3 the size of a smallest progressive representative of any equivalence
class of ∼EFSP ,G,t is at most b(EFSP , g, t, G). Therefore, we can apply Lemma 4 and deduce
that, in time O(|Y |), we can find a t-protrusion Y 0 of size at most b(EFSP , g, t, G) such
that Y ∼EFSP ,G,t Y 0 and the corresponding transposition constant ∆EFSP ,t (Y 0 , Y ) with
∆EFSP ,t (Y 0 , Y ) 6 0. Since EFSP is a Π-encoder and ∼∗E ,G,t is DP-friendly, it follows
FSP
from Lemma 2 that Y ≡Π Y 0 and that ∆Π,t (Y 0 , Y ) = ∆EFSP ,t (Y 0 , Y ) 6 0. Therefore, if
we set k 0 := k + ∆Π,t (Y 0 , Y ), it follows that (G, k) and ((G − (Y − ∂(Y ))) ⊕ Y 0 , k 0 ) are
indeed equivalent instances of Π with k 0 6 k and |Y 0 | 6 b(EFSP , g, t, G).

A.7

Proof of Corollary 1

For 1 6 i 6 `, where ` is the number of protrusions in the decomposition, we apply
the polynomial-time algorithm given by Theorem 1 to replace each t-protrusion Yi with
a graph Yi0 of size at most b(EFSP , g, t, G) and to update the parameter accordingly.
In this way we obtain an equivalent instance (G0 , k 0 ) such that G0 ∈ G, k 0 6 k and
|V (G0 )| 6 |Y0 | + ` · b(EFSP , g, t, G) 6 (1 + b(EFSP , g, t, G))α · k .

43

