# 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.

• Hint (not sure this is on the right track, but it's what I'd try): [EDIT: In the reduced problem in which the maximum degree is $k+d$:] Think about the maximum possible amount of "progress" any single deletion could make towards the goal. If you have a YES-instance, then you know that $k$ times that amount of progress (which is an upper bound on the most progress that $k$ deletions could make) must be sufficient to solve the problem. I think this should yield an upper bound on the vertex count. Oct 18, 2020 at 16:58
• Thanks j_random_hacker , for anyone looking have added answer to my question. Oct 21, 2020 at 15:57

Reduction Rule 1. Let $$V$$ be the set of vertices which are isolated. Convert the instance from $$I = (G,k,d)$$ to $$I^{'} = (G -V, k,d)$$. If $$I^{'}$$ is a yes instance, then so is $$I$$, because adding back the isolated vertices do not add on to the degree of other vertices. And isolated vertices have already have degree 0 ($$\le d$$ as $$d \ge 0$$). And if $$I$$ is a yes instance so is $$I^{'}$$, as $$G-V$$ is a sub-graph of $$G$$, and $$k$$ and $$d$$ remain same across the two instances.

Reduction Rule 2. If a vertex $$v$$ has degree $$\ge k+d+1$$ then it has to be kept in the deletion set. Otherwise $$k+1$$ of its neighbours have to be kept in the deletion set. Which cannot be done, as maximum size of deletion set is $$k$$. Thus after this reduction all vertices will have degree $$\le k+d$$.

Reduction Rule 3 If there are two vertices $$v$$ and $$w$$, such that degree of both of them is $$\le d$$. Then the edge $$vw$$ can be removed converting the instance from $$I = (G, k,d)$$ to $$I^{'} = (G-\{vw\}, k,d)$$. If $$I$$ is a yes instance so is $$I^{'}$$ as $$G-\{vw\}$$ is a sub-graph of $$G$$, with $$k$$ and $$d$$ remaining same across the instances. And if $$I^{'}$$ is a yes instance so is $$I$$, as adding back $$vw$$ can make the degree of $$v$$ and $$w$$ at most $$d$$ (as they initially had degree $$\le d$$).

Rule $$1$$ might be applied after applying Rule $$3$$ as well.

Now considering a graph where vertices with degree $$\le d$$ don't share an edge, no vertex is isolated and and all vertices have degree $$\le k+d$$ (ie. none of the above rules applied). Let $$A$$ be the set of vertices with degree $$\le d$$ and let $$B$$ be the set of vertices with degree $$> d$$. We can argue that $$|B| \le k(k+d) +k$$, otherwise the output is no. Because if $$|B| > k(k+d) +k$$, then as most $$k$$ elements will be chose from $$B$$ for the deletion set, and $$> k(k+d)$$ elements will be left (in $$B$$). And as each of them has degree $$> d$$, they each have at least one edge going into the deletion set. But the deletion set can only accommodate $$k(k+d)$$ edges. Also as each vertex in $$A$$ has at least one neighbor (and all of them in $$B$$), the maximum number of vertices in $$A$$, will be bounded as $$|A| \le |B|(k+d) \le (k(k+d)+k)(k+d) = k(k+d)(k+d+1)$$. So $$|A| + |B| \le k(k+d) + k(k+d)(k+d+1) = k(k+d)(k+d+2)$$.

• the above bound of |B| isn't clear to me, can you please explain it? I'm not sure why the fact that each vertex in B has degree > d, means they each have at least one edge going into the deletion set... thanks Apr 13, 2021 at 13:20
• Let's suppose we have a vertex $v$ with degree $>d$, with no edge going into the deletion set. Then by definition, this is not a deletion set leading to a contradiction. As after removing vertices in the deletion set each vertex left should have bounded degree of $<=d$. Apr 13, 2021 at 13:58
• @sashas any idea how to it on O(k)? (I think Expansion Lemma should be in used here) Jul 14, 2021 at 20:10