Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions

We present a linear-time algorithm to compute a decomposition scheme for graphs

G

that have a set

X

 ⊆ 

V

(

G

), called a

treewidth-modulator

, such that the treewidth of

G

 − 

X

is bounded by a constant. Our decomposition, called a

protrusion decomposition

, is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter

k

) that has

finite integer index

and such that positive instances have a treewidth-modulator of size

O

(

k

) admits a linear kernel on the class of

H

-topological-minor-free graphs, for any fixed graph

H

. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and

H

-minor-free graphs.

Let

$\mathcal{F}$

be a fixed finite family of graphs containing at least one planar graph. Given an

n

-vertex graph

G

and a non-negative integer

k

,

Planar

$\mathcal{F}$

-

Deletion

asks whether

G

has a set

X

 ⊆ 

V

(

G

) such that

$|X|\leqslant k$

and

G

 − 

X

is

H

-minor-free for every

$H\in \mathcal{F}$

. As our second application, we present the first

single-exponential

algorithm to solve

Planar

$\mathcal{F}$

-

Deletion

. Namely, our algorithm runs in time 2

O

(

k

)

·

n

2

, which is asymptotically optimal with respect to

k

. So far, single-exponential algorithms were only known for special cases of the family

$\mathcal{F}$

.