parameterized complexity – Finding a kernel for d-Bounded degree deletion


In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum vertex degree of the graph to at most $d$.

The question is to how to find a polynomial kernel (in $k$ and $d$) for this problem.

I seem to be able to get the only reduction rule that if any vertex has degree $ > k+d$, it has to be there in the deletion set (if the answer to instance is yes). Because if it isn’t, then at least $k+1$ of its neighbors have to be in deletion set. I can’t seem to move beyond this point.

The exercise is from this book (exercise $2.9$).

I am also aware that we can remove edges between vertices with degree $< d$, and find solution in the modified graph (hint from the book). But I am not sure how it will be useful, in getting a bound over number of vertices/edges in $k$ and $d$.

I would appreciate only hints if possible (something maybe beyond the book hints).

PS: for $d=0$ this reduces to vertex cover problem.