Bidimensionality and Kernels
Fedor V. Fomin ∗
Daniel Lokshtanov†
Saket Saurabh‡
Dimitrios M. Thilikos§
Abstract
Bidimensionality theory appears to be a powerful framework
in the development of meta-algorithmic techniques.
It was introduced by Demaine et al. [J. ACM 2005 ] as
a tool to obtain sub-exponential time parameterized algorithms
for bidimensional problems on H-minor free
graphs. Demaine and Hajiaghayi [SODA 2005 ] extended
the theory to obtain polynomial time approximation
schemes (PTASs) for bidimensional problems. In this
paper, we establish a third meta-algorithmic direction for
bidimensionality theory by relating it to the existence of
linear kernels for parameterized problems. In parameterized
complexity, each problem instance comes with a parameter
k and the parameterized problem is said to admit a
linear kernel if there is a polynomial time algorithm, called
a kernelization algorithm, that reduces the input instance
to an equivalent instance (called kernel) with size linearly
bounded by k. We show that “essentially” all bidimensional
problems not only have sub-exponential time algorithms
and PTASs but they also have linear kernels, affirmatively
answering an open question from [J. ACM 2005 ]
where the existence of linear kernels was conjectured for
the first time. In particular, we prove that every minor (respectively
contraction) bidimensional problem that satisfies
the separation property and is of finite integer index,
admits a linear kernel for classes of graphs that exclude a
fixed graph (respectively an apex graph H) H as a minor.
Recently, Bodlaender et al. [FOCS 2009 ] laid the foundation
for obtaining meta-algorithmic results for kernelization
and showed that various problems satisfying some
logical and compactness properties have polynomial, even
linear kernels on graphs of bounded genus. With the use
of bidimensionality we are able to extend these results to
minor-free and apex-minor-free graphs. Our results imply
that a multitude of bidimensional problems, which include
DOMINATING SET, FEEDBACK VERTEX SET, EDGE
DOMINATING SET, VERTEX COVER, r-DOMINATING
SET, CONNECTED DOMINATING SET, CYCLE PACK∗Department
of Informatics, University of Bergen, Norway.
†Department of Informatics, University of Bergen, Norway.
‡The Institute of Mathematical Sciences, CIT Campus, Chennai,
India.
§Department of Mathematics, National & Kapodistrian University
of Athens, Greece. Supported by the project “Kapodistrias”
(AΠ 02839/28.07.2008) of the National and Kapodistrian
University of Athens (project code: 70/4/8757).
ING, CONNECTED VERTEX COVER, ALMOST CONSTANT
TREEWIDTH, and various other vertex covering
and packing problems, admit linear kernels on the corresponding
graph classes. For most of these problems no
polynomial kernels on H-minor-free graphs were known
prior to our work.
1 Introduction
Bidimensionality was introduced as a framework for
designing subexponential parameterized algorithms
on sparse graphs. Alber et al. [2] obtained the
first subexponential parameterized algorithm on planar
graphs by solving the parameterized DOMINATING
SET problem in time 2O(
√
k)
nO(1)
, where n
is the input size. It appeared that not only DOMINATING
SET but many other parameterized problems
are solvable in subexponential time on planar
graphs. The main purpose of Bidimensionality
Theory was to provide a meta-algorithmic description
of all these problems. The theory was
developed by Demaine et al. [17, 18] and it allowed
to unify and extend subexponential fixedparameter
algorithms for NP-hard graph problems
to a broad range of graphs including planar graphs,
map graphs, bounded-genus graphs and graphs excluding
any fixed minor. This theory is build on
cornerstone theorems from Graph Minors Theory of
Robertson and Seymour and its initial purpose was
to serve as a simple criterion of checking whether
a parameterized problem is solvable in subexponential
time on planar graphs, and even more generally,
on graphs excluding some fixed graph as a minor.
Roughly speaking, the problem is bidimensional if
the solution value for the problem on a k × k-grid
is Ω(k2
), and contraction/removal of edges does
not increase solution value. Many natural problems
are bidimensional, including DOMINATING
SET, FEEDBACK VERTEX SET, EDGE DOMINATING
SET, VERTEX COVER, r-DOMINATING SET,
CONNECTED DOMINATING SET, CYCLE PACKING,
CONNECTED VERTEX COVER, GRAPH METRIC
TSP, and many others.
The second application of bidimensionality was
given by Demaine and Hajiaghayi [18] who have
shown that bidimensionality is a useful theory not
only in the design of fast fixed-parameter algorithms
503 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
but also in the design of fast PTASs. They established
a link between parameterized and approximation
algorithms by proving that every bidimensional
problem satisfying some simple separation properties
has a PTAS on planar graphs and other classes
of sparse graphs. We refer to the surveys [15, 20]
for further information on bidimensionality and its
applications.
In this work we give the third application of
bidimensionality—kernelization. Kernelization can
be seen as the strategy of analyzing preprocessing or
data reduction heuristics from a parameterized complexity
perspective. Parameterized complexity is basically
a two-dimensional generalization of “P vs.
NP” where in addition to the overall input size n, one
studies the effects on computational complexity of a
secondary measurement that captures additional relevant
information. This additional information can
be, for example, solution size or a structural restriction
on the input distribution considered, such as a
bound on the treewidth of an input graph. The secondary
information is quantified by a positive integer
k and is called the parameter. Parameterization
can be deployed in many different ways; for general
background on the theory see [21, 22, 30].
A parameterized problem with a parameter k
is said to admit a polynomial kernel if there is a
polynomial time algorithm (the degree of polynomial
is independent of k), called a kernelization algorithm,
that reduces the input instance down to an
instance with size bounded by a polynomial p(k) in
k, while preserving the answer. Kernelization has
been extensively studied in parameterized complexity,
resulting in polynomial kernels for a variety of
problems. Notable examples of known kernels are
a 2k-sized vertex kernel for VERTEX COVER [13],
a 355k kernel for DOMINATING SET on planar
graphs [3], which later was improved to a 67k kernel
[11], and an O(k2
) kernel for FEEDBACK VERTEX
SET [32] parameterized by the solution size.
One of the most intensively studied directions in kernelization
is the study of problems on planar graphs
and other classes of sparse graphs. This study was
initiated by Alber et al. [3] who gave the first linear
sized kernel for the DOMINATING SET problem
on planar graphs. The work of Alber et al. [3]
triggered an explosion of papers on kernelization,
and kernels of linear sizes were obtained for a variety
of parameterized problems on planar graphs including
CONNECTED VERTEX COVER, MINIMUM
EDGE DOMINATING SET, MAXIMUM TRIANGLE
PACKING, EFFICIENT EDGE DOMINATING SET,
INDUCED MATCHING, FULL-DEGREE SPANNING
TREE, FEEDBACK VERTEX SET, CYCLE PACKING,
and CONNECTED DOMINATING SET [3, 8, 9,
12, 25, 26, 27, 28, 29]. Not much was known about
kernelization on more general classes prior to this
paper, except for DOMINATING SET. It was shown
recently that DOMINATING SET enjoys a polynomial
kernel on graphs excluding a fixed graph as a minor
and on graphs of bounded degeneracy [4, 31].
We refer to the survey of Guo and Niedermeier [24]
for a detailed treatment of the area of kernelization.
Since most of the problems known to have polynomial
kernels on planar graphs are bidimensional, the
existence of links between bidimensionality and kernelization
was conjectured and left as an open problem
in [17].
In this work we show that every bidimensional
problem with a simple separation property, which is
a weaker property than the one required in the framework
of Demaine and Hajiaghayi for PTASs [18] and
with finite integer index (we postpone this definition
till the next section) has a linear kernel on planar and
even much more general classes of graphs. In this
paper all the problems are parameterized by the solution
size. Our main result is the following theorem.
THEOREM 1.1. Every minor-bidimensional problem
Π with the separation property and finite integer
index has a linear kernel on graphs excluding
some fixed graph as a minor. Every contractionbidimensional
problem Π with the separation property
and with finite integer index has a linear kernel
on graphs excluding some fixed apex graph as a mi-
nor.
Our approach is built on recent results from
Bodlaender et al. [5] who proved the first metatheorems
on kernelization. It was shown in [5] that
every parameterized problem that has finite integer
index and satisfies an additional surface-dependent
property called quasi-compactness has a linear kernel
on graphs of bounded genus.
Our kernelization algorithm uses only one reduction
rule, which is based on finite integer index
properties of the problem in question. This is exactly
the same reduction rule as the one used in the kernelization
algorithm given in [5] for obtaining kernels
on planar graphs and graphs of bounded genus. The
novel contribution of this paper is the way the kernel
sizes for bidimensional problems are analyzed.
The analysis of kernel sizes in [5] requires “topological”
decompositions of the given graph, in the sense
that the partitioning of the graph into regions with
small border, or protrusions, strongly depends on a
embedding of the graph into a surface. While such
an approach works well when we have a topological
embedding it seems difficult to extend it to graphs
excluding some fixed graph as a minor. Instead of
taking the topological approach, we apply bidimensionality
and suitable variants of the Excluded Grid
504 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
Theorem [16, 19, 23]. This makes our arguments
considerably simpler than the analysis in [5].
2 Definitions and Notations
In this section we give various definitions which we
make use of in the paper. Let G = (V, E) be a graph.
A graph G = (V , E ) is a subgraph of G if V ⊆ V
and E ⊆ E. The subgraph G is called an induced
subgraph of G if E = {uv ∈ E | u, v ∈ V }, in this
case, G is also called the subgraph induced by V
and denoted with G[V ]. By N(u) we denote (open)
neighborhood of u that is the set of all vertices
adjacent to u and by N[u] = N(u)∪{u}. Similarly,
for a subset D ⊆ V , we define N[D] = ∪v∈DN[v]
and N(D) = N[D] \ D. We denote by Kh the
complete graph on h vertices.
2.1 Parameterized algorithms, Kernels and
Treewidth A parameterized problem Π is a subset
of Γ∗
× N for some finite alphabet Γ. An instance
of a parameterized problem consists of (x, k), where
k is called the parameter. We will assume that k is
given in unary and hence k ≤ |x|O(1)
. A central notion
in parameterized complexity is fixed parameter
tractability (FPT) which means, for a given instance
(x, k), solvability in time f(k)·p(|x|), where f is an
arbitrary function of k and p is a polynomial in the
input size. The notion of kernelization is formally
defined as follows.
DEFINITION 2.1. [Kernelization] A kernelization
algorithm, or in short, a kernel for a parameterized
problem Π ⊆ Γ∗
× N is an algorithm that given
(x, k) ∈ Γ∗
×N outputs in time polynomial in |x|+k
a pair (x , k ) ∈ Γ∗
× N such that (a) (x, k) ∈ Π if
and only if (x , k ) ∈ Π and (b) |x |, k ≤ g(k),
where g is some computable function. The function
g is referred to as the size of the kernel. If g(k) =
kO(1)
or g(k) = O(k) then we say that Π admits a
polynomial kernel and linear kernel respectively.
Treewidth. A tree decomposition of a graph
G = (V, E) is a pair (X, T) where T = (VT , ET )
is a tree and X = {Xi | i ∈ VT } is a collection of
subsets of V such that:
1. i∈VT
Xi = V ,
2. for each edge xy ∈ E, {x, y} ⊆ Xi for some
i ∈ VT ;
3. for each x ∈ V the set {i | x ∈ Xi} induces a
connected subtree of T.
The width of the tree decomposition is
maxi∈VT
|Xi| − 1. The treewidth of a graph G is
the minimum width over all tree decompositions of
G. We denote by tw(G) the treewidth of graph G.
2.2 Protrusions, t-Boundaried Graphs and Finite
Integer Index Given a graph G = (V, E) and
S ⊆ V , we define ∂G(S) as the set of vertices in S
that have a neighbor in V \ S. For a set S ⊆ V the
neighborhood of S is NG(S) = ∂G(V \S). When it
is clear from the context, we omit the subscripts. We
now define the notion of a protrusion.
DEFINITION 2.2. [r-protrusion] Given a graph
G = (V, E), we say that a set X ⊆ V is an rprotrusion
of G if |N(X )| ≤ r and tw(G[X ∪
N(X )]) ≤ r.
For an r-protrusion X , the vertex set X =
X ∪ N(X ) is called an extended r-protrusion. The
set X is the extended protrusion of X and X is the
protrusion of X.
We now define the notion of t-boundaried
graphs and various operations on them.
DEFINITION 2.3. [t-Boundaried Graphs] A tboundaried
graph is a graph G = (V, E) with t distinguished
vertices, uniquely labeled from 1 to t. The
set ∂(G) of labeled vertices is called the boundary of
G. The vertices in ∂(G) are referred to as boundary
vertices or terminals.
For a graph G = (V, E) and a vertex set S ⊆
V , we will sometimes consider the graph G[S] as
the |∂(S)|-boundaried graph with ∂(S) being the
boundary.
DEFINITION 2.4. [Gluing by ⊕] Let G1 and G2 be
two t-boundaried graphs. We denote by G1 ⊕G2 the
t-boundaried graph obtained by taking the disjoint
union of G1 and G2 and identifying each vertex of
∂(G1) with the vertex of ∂(G2) with the same label;
that is, we glue them together on the boundaries.
In G1 ⊕ G2 there is an edge between two labeled
vertices if there is an edge between them in G1 or in
G2.
DEFINITION 2.5. [Legality] Let G be a graph
class, G1 and G2 be two t-boundaried graphs, and
G1, G2 ∈ G. We say that G1 ⊕ G2 is legal with respect
to G if the unified graph G1 ⊕ G2 ∈ G. If the
class G is clear from the context we do not say with
respect to which graph class the operation is legal.
DEFINITION 2.6. [Replacement] Let G = (V, E)
be a graph containing an extended r-protrusion X.
Let X be the restricted protrusion of X and let G1
be an r-boundaried graph. The act of replacing
X with G1 corresponds to changing G into G[V \
X ] ⊕ G1. Replacing G[X] with G1 corresponds to
replacing X with G1.
DEFINITION 2.7. For a parameterized problem Π
on a graph class G and two t-boundaried graphs
G1 and G2, we say that G1 ≡Π G2 if there exists
505 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
a constant c such that for all t-boundaried graphs
G3 and for all k: (a) G1 ⊕ G3 is legal if and only if
G2 ⊕ G3 is legal; (b) (G1 ⊕ G3, k) ∈ Π if and only
if (G2 ⊕ G3, k + c) ∈ Π.
DEFINITION 2.8. [Finite Integer Index] We say
that a parameterized problem Π has finite integer
index in a graph class G if for every t there exists
a finite set S of t-boundaried graphs such that S ⊆
G and for any t-boundaried graph G1 there exists
G2 ∈ S such that G2 ≡Π G1. Such a set S is called
a set of representatives for (Π, t).
Note that for every t, the relation ≡Π on tboundaried
graphs is an equivalence relation. A
problem Π is finite integer index, if and only if for
every t, ≡Π is of finite index, that is, has a finite
number of equivalence classes.
2.3 Minors and Contractions Given an edge e =
xy of a graph G, the graph G/e is obtained from
G by contracting the edge e, that is, the endpoints
x and y are replaced by a new vertex vxy which
is adjacent to the old neighbors of x and y (except
from x and y). A graph H obtained by a sequence
of edge-contractions is said to be a contraction of G.
We denote it by H ≤c G. A graph H is a minor of
a graph G if H is the contraction of some subgraph
of G and we denote it by H ≤m G. We say that
a graph G is H-minor-free when it does not contain
H as a minor. We also say that a graph class GH is
H-minor-free (or, excludes H as a minor) when all
its members are H-minor-free. An apex graph is a
graph obtained from a planar graph G by adding a
vertex and making it adjacent to some of the vertices
of G. A graph class GH is apex-minor-free if GH
excludes a fixed apex graph H as a minor.
2.4 Grids and their triangulations. Let r be a
positive integer, r ≥ 2. The (r × r)-grid is the
Cartesian product of two paths of lengths r − 1. A
vertex of a grid is a corner if it has degree 2. Thus
each (r×r)-grid has 4 corners. A vertex of a (r×r)grid
is called internal if it has degree 4, otherwise it
is called external. Let Γr be the graph obtained from
the (r × r)-grid by triangulating internal faces of the
(r × r)-grid such that all internal vertices become
of degree 6, all non-corner external vertices are of
degree 4, and then one corner of degree two is joined
by edges with all vertices of the external face. The
graph Γ6 is shown in Fig. 1.
2.5 Bidimensionality and Separation property
DEFINITION 2.9. ([17, 23]) A parameterized
problem Π is minor-bidimensional if
Figure 1: Graph Γ6.
1. For any pair of graphs H ≤m G and integer
k, (G, k) ∈ Π ⇒ (H, k) ∈ Π. In other words,
contracting or deleting an edge in a graph G
cannot increase the parameter; and
2. there is δ > 0 such that for every (r × r)-grid
R, (R, k) ∈ Π for every k ≤ δr2
. In other
words, the value of the solution on R should be
at least δr2
.
A parameterized problem Π is called contractionbidimensional
if
1. For any pair of graphs H ≤c G and integer k,
(G, k) ∈ Π ⇒ (H, k) ∈ Π, and
2. there is δ > 0 such that (Γr, k) ∈ Π for every
k ≤ δr2
.
In either case, Π is called bidimensional.
DEFINITION 2.10. For a parameterized problem Π,
let Π denote the set of all no instances of Π. A minor
(contraction) bidimensional problem Π is called
a minimization problem if for all (G, k) ∈ Π,
tw(G) ≤ O(
√
k) whenever G excludes a fixed
(apex) graph H as a minor. A minor (contraction)
bidimensional problem Π is called a maximization
problem if for all (G, k) ∈ Π, tw(G) ≤ O(
√
k)
whenever G excludes a fixed (apex) graph H as a
minor.
Demaine and Hajiaghayi [18] define the separation
property for problems, and show how separability
together with bidimensionality is useful to obtain
PTASes on H-minor-free graphs. In our setting
a slightly weaker notion of separability is sufficient.
In particular the following definition is just the requirement
3 of the definition of separability in [18].
DEFINITION 2.11. A minor-bidimensional problem
has the separation property if given any graph G,
given any vertex cut S, and given an optimal solution
OPT to G, for any union G of some subset of
connected components of G \ S, |OPT ∩ G | is
between |OPT(G )| − O(|S|) and |OPT(G )| +
O(|S|).
506 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
For contraction-bidimensional parameters we
have a slightly different definition of the separation
property.
DEFINITION 2.12. A contraction-bidimensional
problem has the separation property if the following
condition is satisfied. Given a graph G, a vertex
cut S whose removal disconnects G into connected
components C1, C2, . . . , Ck, and a subset
I ⊆ {1, 2, . . . , k}, we define GI to be the graph
obtained from G by contracting for every j ∈ I
the component Cj into the vertex in N(Cj) with
the lowest index. Let OPT be an optimal solution
to G. Then for any subset I ⊆ {1, 2, . . . , k},
|OPT ∩ GI| is between |OPT(GI)| − O(|S|) and
|OPT(GI)| + O(|S|).
3 Combinatorial Properties of Separable
Bidimensional Problems
In this section we first show that any non-trivial
instance of a separable bidimensional problem must
have a O(k) sized vertex set whose deletion makes
the treewidth of the input graph constant. Second,
we show how to exploit such a set to find a large
protrusion in the input graph. We need the following
well known lemma, see e.g. [6], on separators in
graphs of bounded treewidth.
LEMMA 3.1. Let G = (V, E) be a graph of
treewidth at most t and w : V → R+
∪ {0} be a
weight function. Then there is a set S ⊂ V of size
at most t + 1 such that for every connected component
G[C] of G[V \ S], w(C) ≤ w(V )/2. Furthermore
the connected components C1, . . . , C of
G[V \ S] can be grouped into two sets C1 and C2
such that w(V )−w(S)
3 ≤ w(Ci) ≤ 2(w(V )−w(S))
3 , for
i ∈ {1, 2}.
We also need the following result proved in
[16, 19, 23].
PROPOSITION 3.1. ([16, 19, 23]) Let G be a connected
graph excluding a fixed graph H as a minor.
Then there exists some constant c such that if
tw(G) ≥ c · r2
, then G contains the r × r-grid as
a minor. Moreover, if H is an apex graph, then G
contains Γr as a contraction.
LEMMA 3.2. Let Π be a minor-bidimensional problem
with the separation property. For every (G =
(V, E), k) ∈ Π, where G does not contain a fixed
graph H as a minor, there is a subset of vertices
S ⊆ V and a constant t, such that |S| = O(k),
and tw(G[V \ S]) ≤ t.
Proof. The definition of minor-bidimensionality together
with Proposition 3.1 imply that for every
(G, k) ∈ Π there is a constant d such that tw(G) ≤
d
√
k. Let us fix a solution Z of size k for G and
a weight function w : V → {0, 1} which assigns
1 to every vertex in Z and 0 otherwise. By
Lemma 3.1, there exists a separator X of G of size
at most d
√
k + 1 such that the connected components
of G[V \ X] can be grouped into two parts C1
and C2 such that k−w(X)
3 ≤ w(Ci) ≤ 2(k−w(X))
3 ,
i ∈ {1, 2}.
We want to construct a set S such that the
treewidth of G[V \ S] is at most t. We start the
construction by putting S := X. Let Z1 and Z2 be
an optimum solution to Π on graphs G1 = G[C1] and
G2 = G[C2] respectively. Since Π is separable, we
have that |Z∩Ci| = |Zi|±O(|X|) for i ∈ {1, 2}. We
grow S by recursively applying Lemma 3.1 to find
balanced separators in G1 and G2 respectively and
adding them to S. Since Π is minor-bidimensional
problem with the separation property, we have that
in recursive step for a graph G with solution of size
we find a separator of size O(
√
). Let µ(G, Z, k)
denote the size of the set S, we are looking for. Then
we get the following recurrence for µ(G, k),
µ(G, Z, k) ≤ µ G1, Z1,
k
3
+ (d
√
k)
+ µ G2, Z2,
2k
3
+ (d
√
k)
+ (d
√
k + 1)
where d and d are constants. We stop recursing
when the solution in the current graph is at most
some fixed constant t . Again, by making use of
Proposition 3.1 and minor-bidimensionality of Π,
we conclude that the treewidth of the graphs at the
leaves of the recursion tree is at most some fixed
constant t. Hence we have found a set S such that
the treewidth of G[V \ S] is at most t. By applying
the generalization of Master’s Theorem due to Akra
and Bazzi [1] to the recurrence above we have that
the size of S is O(k).
The proof of the next lemma for contractionbidimensional
problems Π satisfying the separation
property goes along the proof of Lemma 3.2, with
the only difference that instead of using the first part
of Proposition 3.1, we use the part on contractions.
LEMMA 3.3. Let Π be a contraction-bidimensional
problem with the separation property. For every
(G = (V, E), k) ∈ Π, where G is an apex-minorfree
graph, there is a subset of vertices S ⊆ V and
constant t, such that |S| = O(k) and tw(G[V \
S]) ≤ t.
Proof. The proof of this lemma is almost identical
to the proof of Lemma 3.2. The only difference
is in the definition of the graphs G1 and G2.
507 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
Let C1, C2, . . . , C be the connected components
of G[V \ S] and let Ii ⊆ {1, 2, . . . , } such that
Ci = ∪j∈Ii
Cj. We set G1 := GI1
and G2 := GI2
as in Definition 2.12.
We proceed to show that any H-minor-free nvertex
graph G with a vertex set S of size k such
that tw(G \ S) is constant must have a protrusion
of size at least cn/k for some fixed c. This result is
crucial for our analysis of the kernel sizes.
LEMMA 3.4. For every fixed graph H and constant
t there are constants ζ and r that satisfy the following.
For any n-vertex graph G which excludes H as
a minor and has a vertex set S of size k such that
tw(G \ S) ≤ t, G has an extended r-protrusion of
size at least ζn/k.
Proof. For a fixed graph H and constants t, p and
q define µ(k, x) to be the maximum number of
vertices in a graph G excluding H as a minor,
such that G has a vertex set S of size k such that
tw(G \ S) ≤ t and there is no set Z of size at least
x such that |∂(Z)| ≤ p and |Z ∩ S| ≤ q. We argue
that for p and q chosen sufficiently large compared
to t and H (but chosen independently of k and x),
µ(k, x) = O(kx).
First, consider a graph G excluding H as a
minor, such that G has a vertex set S of size k such
that tw(G\S) ≤ t. We prove that tw(G) = O(
√
k).
By Proposition 3.1, there is a constant d such that G
contains a (d tw(G) × d tw(G))-grid as a minor.
Thus G contains (d tw(G)/(t + 1))2
disjoint (t +
1 × t + 1)-grids as minors. Since the treewidth of
a (t + 1 × t + 1)-grid is t + 1, S must contain at
least one vertex from each of the (t +1 × t +1)-grid
minors. Thus |S| = k ≥ (d tw(G)/(t + 1))2
and
there is a constant d such that tw(G) ≤ d
√
k.
Now, fix a weight function w : V → R+
such
that w(v) = 1 if v ∈ S and w(v) = 0 otherwise.
By Lemma 3.1, there is a partitioning of V into a
separator X of size at most d
√
k + 1 and two sets C1
and C2 such that N(Ci) ⊆ X and |Ci ∩ S| ≤ 2k/3.
Define S1 = S ∩ (C1 ∪ X) and S2 = S ∩ (C2 ∪ X).
Now, for each i ∈ {1, 2}, a subset Z of Ci ∪ X
satisfying |∂(Z)| ≤ p (in G[Ci∪X]) and |Z∩Si| ≤ q
satisfies |∂(Z)| ≤ p (in G) and |Z ∩ Si| ≤ q. Hence
µ(k, x) ≤ µ
k
3
+ (d
√
k) + 1, x
+ µ
2k
3
+ (d
√
k) + 1, x
However, if k + t ≤ p and k ≤ q, then µ(k, x) < x.
Thus, choosing p and q sufficiently large compared
to t and d and applying the generalization of Master’s
Theorem due to Akra and Bazzi [1] to the recurrence
above we have that µ(k, x) = O(kx).
Notice now that a set Z such that |δ(Z)| ≤ p
and |(Z ∩ S)| ≤ q has treewidth at most t + q and
hence is an extended (p+t+q)-protrusion. Choosing
r = p + t + q and ζ to be a constant such that
ζµ(k, x) ≤ kx completes the proof of the lemma.
4 Kernelization for Separable Bidimensional
Problems
In this section we give our kernelization algorithm.
First we give the reduction rule which is applied
exhaustively on the input to reduce its size. This
rule is from [5] and it has been just modified here
to work for graphs excluding a fixed graph H as a
minor and satisfying finite integer index. Finally, in
the last subsection, we prove Theorem 1.1 using the
auxiliary results we have proved so far.
4.1 Reduction Rule The only reduction rule we
apply has the following form:
If there is a constant size separator such
that after its removal we obtain a connected
component of unbounded size and
of constant treewidth, then we replace this
component with a subgraph of constant
size.
We need the following generalization of lemma from
[5] to H-minor free graphs. The proof is almost
identical and we provide it here for completeness.
LEMMA 4.1. ([5] ) Let Π has finite integer index.
Then there exists a constant c(Π, γ) and an algorithm
that given a graph G = (V, E) ∈ GH, an
integer k and an extended γ-protrusion X in G with
|X| > c(Π, γ), runs in time O(|X|) and returns a
graph G∗
= (V ∗
, E∗
) ∈ GH and an integer k∗
such
that |V ∗
| < |V |, k∗
≤ k, and (G∗
, k∗
) ∈ Π if and
only if (G, k) ∈ Π.
Proof. Let S be a set of representatives for (Π, r)
and let c = maxY ∈S |Y |. Similarly, let S be
a set of representatives for (Π, 2r) and let c =
maxY ∈S |Y |. If |X| > 3c we find an extended 2rprotrusion
X ⊆ X such that c < |X | ≤ 3c and
work on X instead of X. This can be done in time
O(|X|) since G[X] has treewidth at most r. From
now on, we assume that |X| ≤ 3c . This initial step
is the only step of the algorithm that does not work
with constant size structures, and hence the running
time of the algorithm is upper bounded by O(|X|).
The algorithm proceeds as follows.
Because Π has finite integer index there is a
graph H = (VH, EH) ∈ S such that H ≡Π G[X].
We show how to compute H from X. Since k
is given in unary, we have that k ≤ |V |p
. Let
kmax = (6c )p
. For every G1 = (V1, E1) ∈ S,
508 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
G2 = (V2, E2) ∈ S and k ≤ kmax we compute
whether (G1 ⊕G2, k ) ∈ Π. For each such triple the
computation can be done in time O((|V1| + |V2|)p
)
since Π has finite integer index [10, 14]. Now, for
every G1 ∈ S and k ≤ (|X| + |V1|)p
we compute
whether (G[X] ⊕ G1, k ) ∈ Π. When all these
computations are done, the results are stored in a
table.
It is not hard to see that H ≡Π G[X] if and
only if there exists a constant c such that for all
G2 ∈ S and k ≤ kmax, (H ⊕ G2, k ) ∈ Π ⇔
(G[X]⊕G2, k +c) ∈ Π. Also, c is the constant such
that for all r-boundaried graphs G2 and and integers
k , (H ⊕ G2, k ) ∈ Π ⇔ (G[X] ⊕ G2, k + c) ∈ Π.
For each H ∈ C we can check whether H ≡Π G[X]
using this condition and the pre-computed table, and
if H ≡Π G[X], find the constant c.
After we have found a H ∈ S and the corresponding
constant c, such that H ≡Π G[X],
we make G∗
from G by replacing the extended rprotrusion
X with H. Also, we set k∗
= k−c. Since
|X| > c and H has at most c vertices, |V ∗
| < |V |.
By the choice of H and c, (G∗
, k∗
) ∈ Π if and only
if (G, k) ∈ Π. This concludes the proof.
4.2 Proof of Theorem 1.1
Proof. [Proof of Theorem 1.1] We give the proof
only for minor-bidimensional problems. The proof
of the theorem for contraction-bidimensional problems
goes along the same line with the only difference
that instead of Lemma 3.2 we need to use
Lemma 3.3.
We first give a proof for a minor bidimensional
problem Π that is also a minimization problem. Let
Π be a bidimensional problem with the separation
property and finite integer index. By Lemma 3.2, for
(G = (V, E), k) ∈ Π, there is a set S ⊆ V and a
constant t, such that |S| ≤ t · k and the treewidth
of GS = G \ S = (VS, ES) is at most t. By
Lemma 3.4, G contains an r-protrusion of size at
least ζ|V |/tk. The reduction algorithm exhaustively
applies Lemma 4.1, with γ = r. Since an irreducible
instance contains no r-protrusion of size at least
c(Π, γ) it follows that an irreducible instance (G =
(V, E), k) ∈ Π must satisfy ζ|V |/tk < c(Π, γ).
Thus |V | is at most k · tc(Π, γ)/ζ = O(k). For the
case that Π is a minor bidimensional maximization
problem an identical argument shows that for any
irreducible instance (G, k) ∈ Π, |V | is at most O(k).
Now we show that our kernelization procedure
runs in polynomial time. Observe that we can find
a protrusion by guessing the boundary which is of
constant size. Once given a protrusion X we can
replace it with an equivalent instance in O(|X|)
time using the Lemma 4.1. This concludes that the
kernelization algorithm runs in polynomial time.
Theorem 1.1 has the following corollary. The
list in the corollary is not exhaustive, and contains
most of the well-known parameterized problems for
which our theorem gives linear kernels.
COROLLARY 4.1. FEEDBACK VERTEX SET, VERTEX
COVER, CONNECTED VERTEX COVER,
EDGE DOMINATING SET, MINIMUM MAXIMUM
MATCHING, ALMOST CONSTANT TREEWIDTH,
CYCLE PACKING and INDEPENDENT SET admit a
linear kernel on H-minor free graphs. DOMINATING
SET, r-DOMINATING SET, EDGE DOMINATING
SET, CONNECTED DOMINATING SET TRIANGLE
PACKING, and INDUCED MATCHING admit a
linear kernel on an apex minor free graphs.
5 Conclusion
In this paper we related the meta-algorithmic theory
of bidimensionality and the field of kernelization
and affirmatively resolved an open question raised
in [17]. In particular, we showed that every minor
(contraction) bidimensional problems satisfying
a separation property admit a linear kernel on graphs
excluding a fixed graph (apex graph) H as a minor.
Our results have two advantages over the linear
sized kernels obtained in [5]. First, our results apply
to much larger classes of sparse graphs, second our
kernels are obtained using relatively simple combinatorial
arguments instead of an approach based on
topological decomposition. The requirement of separability
in addition to bidimensionality is unavoidable,
as k-PATH, the problem of finding a k-sized
path in the given graph, is bidimensional but it is
known not to admit polynomial kernel even on planar
graphs unless the polynomial hierarchy collapses
to the third level [7].
We conclude the article with an open problem
- do all ”reasonable“ contraction-bidimensional
parameters have linear kernels on H-minor-free
graphs? In particular, does DOMINATING SET and
CONNECTED DOMINATING SET?
References
[1] M. AKRA AND L. BAZZI, On the solution of linear
recurrence equations, Computational Optimization
and Applications, 10 (1998), pp. 195–210.
[2] J. ALBER, H. L. BODLAENDER, H. FERNAU,
T. KLOKS, AND R. NIEDERMEIER, Fixed parameter
algorithms for dominating set and related problems
on planar graphs, Algorithmica, 33 (2002),
pp. 461–493.
[3] J. ALBER, M. R. FELLOWS, AND R. NIEDERMEIER,
Polynomial-time data reduction for dominating
sets, J. ACM, 51 (2004), pp. 363–384.
509 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.
[4] N. ALON AND S. GUTNER, Kernels for the dominating
set problem on graphs with an excluded minor,
Tech. Rep. TR08-066, Electronic Colloquium
on Computational Complexity (ECCC), 2008.
[5] H. BODLAENDER, F. V. FOMIN, D. LOKSHTANOV,
E. PENNINKX, S. SAURABH, AND D. M. THILIKOS,
(Meta) kernelization, in FOCS’09, IEEE
Comput. Soc. Press, 2009, p. to appear.
[6] H. L. BODLAENDER, A partial k-arboretum of
graphs with bounded treewidth, Theor. Comp. Sc.,
209 (1998), pp. 1–45.
[7] H. L. BODLAENDER, R. G. DOWNEY, M. R. FELLOWS,
AND D. HERMELIN, On problems without
polynomial kernels, in Proc. 35th ICALP, vol. 5125
of LNCS, Springer, 2008, pp. 563–574.
[8] H. L. BODLAENDER AND E. PENNINKX, A linear
kernel for planar feedback vertex set, in Proceedings
Third International Workshop on Parameterized and
Exact Computation, IWPEC 2008, M. Grohe and
R. Niedermeier, eds., Springer Verlag, Lecture Notes
in Computer Science, vol. 5018, 2008, pp. 160–171.
[9] H. L. BODLAENDER, E. PENNINKX, AND R. B.
TAN, A linear kernel for the k-disjoint cycle problem
on planar graphs, in Proceedings of the 19th International
Symposium on Algorithms and Computation
(ISAAC), vol. 5369 of LNCS, Springer, 2008,
pp. 306–317.
[10] H. L. BODLAENDER AND B. VAN ANTWERPENDE
FLUITER, Reduction algorithms for graphs of
small treewidth, Information and Computation, 167
(2001), pp. 86–119.
[11] J. CHEN, H. FERNAU, I. A. KANJ, AND G. XIA,
Parametric duality and kernelization: Lower bounds
and upper bounds on kernel size, in Proc. 22nd
STACS, vol. 3404 of LNCS, Springer, 2005,
pp. 269–280.
[12] , Parametric duality and kernelization: Lower
bounds and upper bounds on kernel size, SIAM J.
Comput., 37 (2007), pp. 1077–1106.
[13] J. CHEN, I. A. KANJ, AND W. JIA, Vertex Cover:
Further observations and further improvements,
J. Algorithms, 41 (2001), pp. 280–301.
[14] B. DE FLUITER, Algorithms for Graphs of Small
Treewidth, PhD thesis, Utrecht University, 1997.
[15] E. DEMAINE AND M. HAJIAGHAYI, The bidimensionality
theory and its algorithmic applications,
The computer Journal, (2007), pp. 332–337.
[16] E. D. DEMAINE, F. V. FOMIN, M. HAJIAGHAYI,
AND D. M. THILIKOS, Bidimensional parameters
and local treewidth, SIAM J. Discrete Math., 18
(2004/05), pp. 501–511.
[17] E. D. DEMAINE, F. V. FOMIN, M. HAJIAGHAYI,
AND D. M. THILIKOS, Subexponential parameterized
algorithms on bounded-genus graphs and Hminor-free
graphs, J. ACM, 52 (2005), pp. 866–893.
[18] E. D. DEMAINE AND M. HAJIAGHAYI, Bidimensionality:
New connections between FPT algorithms
and PTASs, in Proc. 16th SODA, ACM/SIAM, 2005,
pp. 590–601.
[19] E. D. DEMAINE AND M. HAJIAGHAYI, Linearity of
grid minors in treewidth with applications through
bidimensionality, Combinatorica, 28 (2008), pp. 19–
36.
[20] F. DORN, F. V. FOMIN, AND D. M. THILIKOS,
Subexponential parameterized algorithms, Comp,
Sc. Rev., 2 (2008), pp. 29–39.
[21] R. G. DOWNEY AND M. R. FELLOWS, Parameterized
Complexity, Springer, 1999.
[22] J. FLUM AND M. GROHE, Parameterized Complexity
Theory, Texts in Theoretical Computer Science.
An EATCS Series, Springer-Verlag, Berlin, 2006.
[23] F. V. FOMIN, P. A. GOLOVACH, AND D. M. THILIKOS,
Contraction bidimensionality: the accurate
picture, in ESA’09, LNCS, 2009, p. to appear.
[24] J. GUO AND R. NIEDERMEIER, Invitation to
data reduction and problem kernelization, SIGACT
News, 38 (2007), pp. 31–45.
[25] , Linear problem kernels for NP-hard problems
on planar graphs, in Proc. 34th ICALP,
vol. 4596 of LNCS, Springer, 2007, pp. 375–386.
[26] J. GUO, R. NIEDERMEIER, AND S. WERNICKE,
Fixed-parameter tractability results for full-degree
spanning tree and its dual, in Proceedings of the Second
International Workshop on Parameterized and
Exact Computation (IWPEC), vol. 4169 of LNCS,
Springer, 2006, pp. 203–214.
[27] I. A. KANJ, M. J. PELSMAJER, G. XIA, AND
M. SCHAEFER, On the induced matching problem,
in Proceedings of the 25th Annual Symposium on
Theoretical Aspects of Computer Science (STACS
2008), vol. 08001, Internationales Begegnungs- und
Forschungszentrum fuer Informatik (IBFI), Schloss
Dagstuhl, Germany, Berlin, 2008, pp. 397–408.
[28] D. LOKSHTANOV, M. MNICH, AND SAURABH,
Linear kernel for planar connected dominating set,
in Proceedings of Theory and Applications of Models
of Computation, (TAMC 2009), Lecture Notes in
Comput. Sci., Springer, 2009.
[29] H. MOSER AND S. SIKDAR, The parameterized
complexity of the induced matching problem in planar
graphs, in Proceedings First Annual International
WorkshopFrontiers in Algorithmics (FAW),
vol. 4613 of LNCS, Springer, 2007, pp. 325–336.
[30] R. NIEDERMEIER, Invitation to fixed-parameter algorithms,
vol. 31 of Oxford Lecture Series in Mathematics
and its Applications, Oxford University
Press, Oxford, 2006.
[31] G. PHILIP, V. RAMAN, AND S. SIKDAR, Polynomial
kernels for dominating set in Ki,j -free and ddegenerate
graphs, manuscript, 2009.
[32] S. THOMASS ´E, A quadratic kernel for feedback
vertex set, in Proc. 20th SODA, ACM/SIAM, 2009,
pp. 115–119.
510 Copyright © by SIAM.
Unauthorized reproduction of this article is prohibited.