Bidimensionality and Kernels

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 Packing, 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.