# Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete

I want to show that a subproblem of the known, $$\mathcal {NP}$$-Complete, Sparse Subgraph problem is also $$\mathcal {NP}$$-Complete.

Sparse Subgraph problem:

Input: Undirected graph $$G(V,E)$$, two integers $$k, l$$.

Output: Is there a subset $$S \subseteq V$$, where $$|S| \geq k$$, such that there are at most $$l$$ edges between pairs of vertices in $$S$$?

My subproblem is the special case where $$k=l$$:

Subproblem of the Sparse Subgraph problem:

Input: Undirected graph $$G(V,E)$$, an integer $$k$$.

Output: Is there a subset $$S \subseteq V$$, where $$|S| \geq k$$, such that there are at most $$k$$ edges between pairs of vertices in $$S$$?

We can easily show that the first one (Sparse Subgraph) is $$\mathcal {NP}$$-Complete, by reducing the Independent Set problem to it.

I tried to reduce the Independent Set problem, as well, to the subproblem without success.

Is there another known $$\mathcal {NP}$$-Complete problem, which I can reduce to the subproblem?

Is the assumption, that the subproblem must also be $$\mathcal {NP}$$-Complete, as it is a special case of the original Sparse Subgraph problem, correct?

I would appreciate any help.

• Hi. Please also credit the source from where you got this problem. Jan 30, 2022 at 15:17
• Answer to your second question: The assumption: "that the subproblem must also be NP-Complete, as it is a special case of the original Sparse Subgraph problem" is incorrect! Jan 30, 2022 at 16:39
• Thank you. The problem occurred from a class discussion in my algorithms course. Jan 30, 2022 at 17:34

Let the independent set problem be $$\mathsf{IS}$$, and the subproblem of the sparse subgraph problem be $$\mathsf{SIS}$$.

The Independent set problem is hard to approximate within any constant factor (see here). It means, it is NP-hard to distinguish between the following instances:

1. Yes Instances: The graphs that contain an independent set of size at least $$k$$

2. No Instance: The graphs that do not contain any independent set of size $$c \cdot k$$ for any constant $$c<1$$.

Using it, we show NP-hardness of $$\mathsf{SIS}$$. That is, we show that it is NP-hard to distinguish between the following instances:

1. Yes Instances: The graphs that contain a set $$S \subseteq V$$ of size at least $$k$$ and with at most $$k$$ edges in $$S$$.

2. No Instance: The graphs that do not contain a set $$S \subseteq V$$ of size at least $$k$$ and with at most $$k$$ edges in $$S$$.

Proof: (->) If $$(G,k)$$ is a yes instance of $$\mathsf{IS}$$ then $$(G,k)$$ is a yes instance of $$\mathsf{SIS}$$. It is trivial.

(<-) We have to show that if $$(G,k)$$ is a no instance of $$\mathsf{IS}$$ then $$(G,k)$$ is a no instance of $$\mathsf{SIS}$$. For the sake of contradiction, assume that $$(G,k)$$ is a yes instance for $$\mathsf{SIS}$$. That is, $$G$$ contains a set $$S \subseteq V$$ of size at least $$k$$ and with at most $$k$$ edges in $$S$$. Let there be $$m$$ edges in $$S$$. Then, there exists a subset $$S' \subseteq S$$ of size $$t \cdot m$$ for $$1\leq t \leq 2$$, that contains the $$m$$ edges. Then we make the following claim:

$$S'$$ contains an independent set of size at least $$m/4$$.

The proof of the above claim follows from Theorem 3.14 in this thesis. Furthermore, the above claim implies that $$S$$ contains an independent set of size at least $$m/4 + (|S|-|S'|) \geq |S'|/8 + (|S|-|S'|) \geq |S|/8$$. That is, $$G$$ contains an independent set of size $$k/8$$. It contradicts that $$G$$ does not have any independent set of size $$c \cdot k$$ for $$c = 1/8$$.

• @entechnic Thanks for pointing out the mistakes. I have edited the answer. Feb 3, 2022 at 18:34
• @JohnL. Thanks a lot for pointing out the mistakes. I have fixed them. But $c$ should be $1/8$. I do not understand why you said $c = 1/2$. Feb 3, 2022 at 20:49
• "The independent set problem" "$\mathsf{IS}$" is, by convention, defined as "the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise". The no instance should be $(G,k)$'s such the $G$ does not contain an independent set of size at least $k$". Apparently, you are not talking about the standard $\mathsf{IS}$ in "If $(G,k)$ is a no instance of $\mathsf{IS}$ ". Or are you? Feb 3, 2022 at 22:13
• @JohnL. Yes. You are right. Thanks! I should use a different name for it. I will edit the post when I get time. Feb 11, 2022 at 8:37