In Special Vertex Cover, we are given an undirected graph $G$, and an integer $k\in \mathbb{N_0}$. The objective is to decide whether there exists a vertex cover $S$ of $G$ of size at most $k$ such that $G[S]$ (the subgraph of G induced by S) has minimum degree 1 i.e the at the subgraph that induced only by the vertices of $S$ there are no isolated vertices.

I want to design an $O(4^k)$-sized kernel for Special Vertex Cover. but I'm stuck because any reduction rule that I'm trying to apply doesn't save the equivalent of one of the requirements. if I try to remove only 1 vertex at a time the requirement that the minimum degree 1 doesn't save. and if I try to remove 2 vertices the requirement that the set will be at size k doesn't save.

so far I've figured that:

  1. if there is an isolated vertex then I need to remove it.
  2. if there 2 isolated neighbors then I need to remove them and decrease k by 2.

what else can do?

  • $\begingroup$ Does it really require minimum degree equal to 1? Or is it that the minimum degree must be at least 1? If it requires equal to 1, why not apply your reduction and then just add a vertex or two at the end? $\endgroup$
    – JimN
    Nov 26, 2021 at 19:40
  • $\begingroup$ @JimN the minimum degree most ti be at least 1 i.e there are not isolated vetexs $\endgroup$
    – OriFrid
    Nov 26, 2021 at 19:44
  • $\begingroup$ If the minimum degree must be 1 or higher, then why is rule(1) (removing all isolated vertices) not sufficient for your needs? $\endgroup$
    – JimN
    Nov 27, 2021 at 3:58
  • $\begingroup$ @JimN No the graph induced by the solution has a minimum degree of 1. $\endgroup$
    – OriFrid
    Nov 27, 2021 at 9:23
  • 1
    $\begingroup$ @ArturRiazanov Still may be a solution becuse there are not a edge to cover in case of isolated vertex. $\endgroup$
    – OriFrid
    Nov 27, 2021 at 12:10

1 Answer 1


Reduction Rule: Let $T$ be the set of vertices such that each vertex has a degree of at least $k+1$ and for every vertex $u \in T$ there exist a vertex $v \in T$ such that there is an edge $(u,v) \in E$. All the vertices in $T$ belong to the vertex cover and already satisfy the "degree $1$" condition. Merge all the vertices in $T$. Let the merged vertex be $t$. Add a new vertex $w$ with $k$ pendant vertices and add an edge $(t,w)$ to the graph. Decrease $k$ by $|T|-2$.

Let $A \subseteq V \setminus T$ be the set of vertices each with a degree of at least $k+1$. Then, $A$ forms an independent set and $|A| \leq k$.

Let $B = V \setminus (A \cup T)$. Then, every vertex in $B$ has a degree at most $k$. Therefore, the graph spanned by $B$ contains at most $k^2$ edges; otherwise, the graph is a "no" instance. Let $B' \subseteq B$ be the set of vertices spanned by these edges. The remaining vertex set $R = B \setminus B'$ forms an independent set. Therefore, $A$ and $R$ form a bipartite graph. Let $x$ and $y$ be two vertices in $R$ that share the same set of neighbors in $A$. Then, one of these vertices can be removed. Using this reduction, the size of $R$ can be reduced to $2^k$. Overall, the number of vertices in the reduced graph is at most $2^k + O(k^2) = O(2^k)$. And, the number of edges is at most $O(k \cdot 2^k)$. I think the number of edges can be further reduced to $O(2^k)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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