# complexity theory – 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.