Prove that finding largest subset of undirected graph that is almost independent is NP-hard

Question

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?

Answer 1

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

Answer 2

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.

[1]-https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

Answer 3

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.