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?

$\endgroup$

1 Answer 1

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$.

$\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 Meyers
    Jan 16 at 6:14
  • 1
    $\begingroup$ @SidMeyers I have added more details. $\endgroup$ Jan 16 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.