2
$\begingroup$

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?

$\endgroup$
12
  • 1
    $\begingroup$ Please state more clearly (better, formally) what you want. There are at least 2 interpretations of your text, with opposite answers. $\endgroup$
    – Dmitry
    Jun 5, 2023 at 4:49
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Jun 5, 2023 at 5:03
  • $\begingroup$ @Dmitry I have edited the question. Hope it is better now $\endgroup$
    – giochi
    Jun 5, 2023 at 7:12
  • $\begingroup$ If $|I|=n$ constraint is present in your $\alpha$-BIVC version, then the answer is trivially "no". $\endgroup$
    – Dmitry
    Jun 5, 2023 at 9:08
  • $\begingroup$ @Dmitry But why? $n$ is not a constant $\endgroup$
    – giochi
    Jun 5, 2023 at 9:13

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

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.