Linear kernels and single-exponential algorithms via protrusion decompositions

A t-treewidth-modulator of a graph G is a set X ⊆ V (G) such that the treewidth of G−X is at most t − 1. In this paper, we present a novel algorithm to compute a decomposition scheme for graphs G that come equipped with a t-treewidth-modulator. Similar decompositions have already been explicitly or implicitly used for obtaining polynomial kernels [3, 7, 33, 43]. 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 is treewidth-bounding admits a linear kernel on the class of H-topological-minor-free graphs, where H is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a t-treewidth-modulator of size O(k), for some constant t. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [7] and H-minor-free graphs [37]. In particular, we show that Chordal Vertex Deletion, Interval Vertex Deletion, Treewidth-t Vertex Deletion, and Edge Dominating Set have linear kernels on H-topological-minor-free graphs