# Maximum independent subset for graphs with lots of edges

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?

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$$.
• 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$? Jan 16 at 6:14