A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.

For these types of problems, I know that I should try to find a polynomial time reduction of an algorithm that is already known to be NP-hard. I tried my hand at trying to manipulate the k-coloring problem, but without any luck.

How would I go about proving this function is NP-hard?


The proof is by reduction from independent set. Given an instance $(G,k)$ of independent set, construct a new instance $(G',1000k)$ in the following way: each vertex $x \in G$ is replaced by an independent set $I_x$ of size 1000, and each edge $(x,y)$ is replaced by a complete bipartite graph $I_x \times I_y$.

If $G$ contains an independent set $S$ of size $k$, then $G'$ contains an independent set $\bigcup_{x \in S} I_x$ of size $1000k$. In the other direction, suppose that $G'$ contains an almost independent set $S$ of size $1000k$. Remove all vertices incident to any edges within $S$ to obtain an independent set $S' \subseteq S$ of size at least $1000k-200$. Let $T = \{ x : I_x \cap S' \neq \emptyset \}$, and note that $T$ is an independent set of $G$. Finally, since $S'$ can contain at most 1000 vertices from each $I_x$, we see that $|T| \geq \lceil |S'|/1000 \rceil = k$.

  • $\begingroup$ I am gonna give you the bounty. The answer of user3563894 only shows Cook hardness. Although it can be more generic and easily instantiated to other notions of graph theory, it lacks the specific features of a reduction like yours. $\endgroup$ Sep 6 '18 at 1:05

The following proof shows that the almost independent set problem is hard using a Cook reduction.

It is well-known that approximating the independent set problem is hard within every polynomial factor [1].

Suppose that if there is a polynomial algorithm for the almost independent set problem, then there is an $x-100$-approximation (i.e., the algorithm returns an independent set of size larger than or equal to $n_{opt}-100$, where $n_{opt}$ is the size of the optimal independent set) polynomial algorithm for the independent set problem. Thus, the problem is NP-hard.

The approximation algorithm for the independent set problem goes as follows:

1) Derive the largest almost independent set $S$.

2) Remove from $S$ all vertices that share the same edge. Denote the result by $S'$

3) Return $S'$.

The algorithm runs in polynomial time.

Correctness: Let $S_{opt}$ be the largest independent set. Then

$$|S'|\geq |S|-100\geq |S_{opt}|-100.$$

The first inequity follows as remove up to 100 vertices. The second inequity follows as every independent set is also an almost independent set, and thus the size of the largest independent set is smaller than or equal to the size of the largest almost-independent set.

Thus, the algorithm is a $x-100$ approximation for the independent set problem, and unless P=NP, there is no polynomial algorithm for the almost independent set problem.


  • $\begingroup$ So, the decision version should be Turing hard for $NP$. Or, could you elaborate to have a Karp reduction? That would be great! $\endgroup$ Sep 5 '18 at 14:27
  • $\begingroup$ For the decision problem, it can be shown using a Gap reduction ( which is similar to a Karp reduction) the hardness of the problem. $\endgroup$ Sep 5 '18 at 14:31
  • $\begingroup$ en.wikipedia.org/wiki/Gap_reduction $\endgroup$ Sep 5 '18 at 14:31
  • $\begingroup$ Note that the above reduction is a Cook Reduction, which uses the algorithm of the largest almost independent set to derive an approximation for the independent set problem. $\endgroup$ Sep 5 '18 at 14:39

My bounty is gonna be over in 7 days. Anyone with clever idea?

This answer is wrong. And I have no idea how to prove this to be complete for $NP$ in any sense.

If only 1 edge is allowed in the almost-IS, then by complementing, this is Karp-complete as shown here.

Even for 2 edges allowed, the hardness of this problem is very elusive.

But if two missing edges are required to be incident to one vertex, then a gadget of one edge and one vertex being connected to all $V$ will show Karp-completeness.

This is Turing complete for $NP$ by a Turing poly-time reduction trying to add each of the $O((n^2-|E|)^{100})$ possible $100$-subsets of $\bar E$ (the complement of $E$ in $G$) and query the almost-clique oracle whether the denser graph has a $k$-almost clique. Since, for each query we add only $100$ edges if one of the query return YES, return YES. Otherwise, return NO.

For Karp completeness, I have not been able to devise any NICE gadget.

  • $\begingroup$ Please see my answer above $\endgroup$ Sep 5 '18 at 13:32

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.