2
$\begingroup$

Consider an NP-hard graph problem, like the maximum independent set problem.

Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. In other words, the graphs are very connected.

Is the maximum independent set problem still hard for these graphs?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ and $V'$ forms a complete graph. Also, there are no edges between $V$ and $V'$. Let the new graph be $G' = (V' \cup V, E')$ which is also a hard instance. And, $|V' \cup V| = 2n$ and $|E'| = \Theta(n^2)$.

Formally, it holds that $G$ has an independent set off size $k$ if and only if $G'$ has an independent set of size $k+1$.

Even if you add edges between every vertex of $V$ and every vertex of $V'$, the reduced instance would be a hard instance. Then, it holds that $G$ has an independent set of size $k$ if and only if $G'$ has an independent set of size $k$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When you mean "For example, take a hard instance $G = (V,E)$ for the problem." in the first line, do you mean take a hard instance of the original maximum independent set problem? Also, is there any edge between the vertices in $V'$ and the vertices in $V$? $\endgroup$
    – Sid Meier
    Jan 16, 2022 at 6:14
  • 1
    $\begingroup$ @SidMeyers I have added more details. $\endgroup$
    – Inuyasha Yagami
    Jan 16, 2022 at 6:27

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.