# Adding edges to enlarge vertex cover

Given a graph $$G=(V,E)$$, and two positive integers $$k$$ and $$\gamma$$, decide if there is a set of new edges to be added such that $$|E'|=k$$, $$E' \cap E = \emptyset$$ and any subset $$V'\subseteq V$$ of size $$\gamma$$ is not a vertex cover of $$(V, E\cup E')$$.

i.e., can we add $$k$$ edges to ensures that the minimum vertex cover has a size at least $$\gamma+1$$.

Clearly, this problem is co-$$NP$$-hard, even for $$k=0$$, as this is then the negation of the regular vertex-cover problem. But for general $$k$$, does this problem allow any approximation algorithms?

• Is this homework? Can you reference the place where you saw this problem? What did you try so far? Commented Jun 7 at 18:18
• No, not a homework assignment. But have been thinking about this for a small project. Initial thoughts were based on thinking that. $\Sigma_2^p$ complexity class typically containing a meta problem, whose "yes" instances, typically call for a "no" instance of an $NP$-complete problem. That lead to discussions on approximating some of them. Vertex cover (unlike stable set/clique etc) allow nice constant-factor approximations. Now, what if we consider a problem in $\Sigma_2^p$ etc. So, a bit fluid that way. Possibly, it is the case, that no approximation is possible. Commented Jun 7 at 18:30
• Related question: cs.stackexchange.com/questions/168479/… Commented Jun 7 at 18:36