Solving Dominating Set in Larger Classes of Graphs: {FPT} Algorithms and Polynomial Kernels

We show that the \nounk-Dominating Set} problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j as a subgraph, for any fixed i,j≥1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded-degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner