1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Hi. Please also credit the source from where you got this problem. $\endgroup$ Jan 30, 2022 at 15:17
  • $\begingroup$ 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! $\endgroup$ Jan 30, 2022 at 16:39
  • $\begingroup$ Thank you. The problem occurred from a class discussion in my algorithms course. $\endgroup$
    – entechnic
    Jan 30, 2022 at 17:34

1 Answer 1

0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @entechnic Thanks for pointing out the mistakes. I have edited the answer. $\endgroup$ Feb 3, 2022 at 18:34
  • $\begingroup$ @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$. $\endgroup$ Feb 3, 2022 at 20:49
  • $\begingroup$ "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? $\endgroup$
    – John L.
    Feb 3, 2022 at 22:13
  • $\begingroup$ @JohnL. Yes. You are right. Thanks! I should use a different name for it. I will edit the post when I get time. $\endgroup$ Feb 11, 2022 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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