4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 18 '20 at 16:58
  • $\begingroup$ Thanks j_random_hacker , for anyone looking have added answer to my question. $\endgroup$
    – sashas
    Oct 21 '20 at 15:57
5
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Apr 13 at 13:20
  • $\begingroup$ 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$. $\endgroup$
    – sashas
    Apr 13 at 13:58
  • $\begingroup$ @sashas any idea how to it on O(k)? (I think Expansion Lemma should be in used here) $\endgroup$
    – GO VEGAN
    Jul 14 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.