# Budgeted Independent Vertex Cover

Suppose that we are given a graph $$G = (V,E)$$ and a number $$n$$. The problem is to find an independent set $$I$$ with $$|I| = n$$, such that number of vertices covered by $$I$$ is maximized (that is, the number of vertices adjacent to at least on vertex from $$I$$). My question: suppose that this problem's name is $$\tt{BIVC}$$; is there $$\alpha<1$$ such that the problem $$\alpha$$-$$\tt{BIVC}$$ (finding independent set that covers $$\alpha\cdot m$$ vertices, where $$m$$ -- is the maximum, i.e. the solution of $$\tt{BIVC}$$) is $$\mathbf{NP}\text{-}\mathbf{hard}$$? Can you give a hint?

• Please state more clearly (better, formally) what you want. There are at least 2 interpretations of your text, with opposite answers. Jun 5, 2023 at 4:49
• I don't understand what your question is. Can you edit your post to state the question more clearly? Do you want an approximation algorithm for this problem? Do you want to know if the problem is NP-hard? Something else? What do you mean by "easiest approximation factor"? Can you define that phrase? Where did you encounter this problem? Can you credit the source where you saw it? Or, what is the motivation?
– D.W.
Jun 5, 2023 at 5:03
• @Dmitry I have edited the question. Hope it is better now Jun 5, 2023 at 7:12
• If $|I|=n$ constraint is present in your $\alpha$-BIVC version, then the answer is trivially "no". Jun 5, 2023 at 9:08
• @Dmitry But why? $n$ is not a constant Jun 5, 2023 at 9:13

Hint: Finding an independent set of size $$n$$ is $$\mathsf{NP}$$-hard.
This much is sufficient to prove that your problem is $$\mathsf{NP}$$-hard as well.