# Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]

The following variation on the vertex cover problem was given:

Given is an instance of graph $$G = (V, E)$$. Does $$G$$ have a vertex cover of size at most $$\frac{|V|}{4}$$?

I was asked to prove that this problem is also $$\mathsf{NP}$$-hard. I am pretty sure that this can be done by using Karp-reduction from the original vertex cover problem to this variation.

That means that I would need some transformation function $$f$$ that would transform an instance of the vertex cover problem, $$I = (V, E, k)$$, to an instance of the above described problem, $$f(I) = (V', E')$$.

I am not sure how to come up with the proper transformation function, but this is what I think have figured out:

• Let $$V = \{v_1, v_2, ..., v_n\}$$.
• Let $$V' = V \cup V^+$$, where $$V^+ = \{v_{n+1}, v_{n+2}, ..., v_{4n}\}$$, because this would mean that the total size $$|V'| = 4 \cdot |V|$$.
• Let $$E' = E \cup E^+$$, where $$E^+ = \{\{v_i, v_j\} \mid v_i \in V, v_j \in V^+, j \in \{n +i, 2n+i, 3n+i\}\}$$. Basically, this means that each vertex in $$V$$ is connected to three different vertices in $$V^+$$ such that all vertices in $$V^+$$ are connected to exactly one vertex in $$V$$.

However, I am having a hard time proving the correctness of this reduction. I think I messed up the generation of $$E'$$, which would make the transformation function wrong. Anyone have an idea what the actual transformation function could be?

## marked as duplicate by xskxzr, David Richerby complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Feb 28 at 11:10

One note is that you'll have to use $$k$$ in your transformation.

Here's one approach that I think works:

We want some $$G' = (V', E')$$ that has a vertex cover of size $$\le \frac{|V'|}{4}$$ iff $$G$$ has a vertex cover of size $$\le k$$.

If $$k = \frac{|V|}{4}$$, just set $$G' = G$$.

When $$k \neq \frac{|V|}{4}$$, one idea is to add a disconnected graph $$H$$ to $$G$$, where we know the vertex cover size of $$H$$.

Case 1: $$k > \frac{|V|}{4}$$. Then we want to add a graph with a small vertex cover. A star graph should do it. A star graph $$H$$ with $$m$$ vertices has vertex cover size $$1$$.

Set $$G' = G \cup H$$, a graph with $$|V| + m$$ vertices. It has vertex cover of size $$\le k+1$$ iff $$G$$ has a vertex cover of size $$\le k$$.

What should $$m$$ be? Let's solve

$$\frac{k + 1}{|V| + m} = \frac{1}{4}$$

This gives $$m = 4(k+1)-|V|$$. So when $$k > \frac{|V|}{4}$$, add a disconnected $$[4(k+1)-|V|]$$-vertex star graph to $$G$$, and call the $$\frac{|V|}{4}$$ vertex cover algorithm on that. $$\square$$

Case 2: $$k < \frac{|V|}{4}$$, we can add a complete graph with some properly chosen number $$m$$ vertices*. Will leave it at that.

*In this case when you solve for $$m$$, $$m$$ may not always be an integer; this can be dealt with by adding a $$\lceil m \rceil$$-vertex complete graph, which "overshoots" a bit, and then adding a small star graph

[Let me know for further clarification/etc]