Polynomial Kernels for Dominating Set in $K_{i,j}$-free and d-degenerate Graphs
Geevarghese Philip, Venkatesh Raman, Somnath Sikdar · 2009
We show that for any fixed i, j ≥ 1, the k-Dominating Set problem restricted to graphs that do not have Ki,j as a subgraph is fixed parameter tractable (FPT) and has a polynomial kernel. This result implies that this problem restricted to bounded-degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner in [3]. Our result extends the class of graphs for which the k-Dominating Set problem is known to have (1) FPT algorithms and (2) polynomial kernels, to the class of Ki,j-free graphs.