1.2k views

Consider the following two problems on undirected graphs:

• $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size |V| - $4$?
• $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$?

Which one of the following is TRUE?

1. $\alpha$ is in P and $\beta$ is NP-complete

2. $\alpha$ is NP-complete and $\beta$ is in P

3. Both $\alpha$ and $\beta$ are NP-complete

4. Both $\alpha$ and $\beta$ are in P

recategorized | 1.2k views
+1
That's the same question from me, WHY? Who told it is NPC?
0
Sir ,answ was given NPC on the below link :

http://geeksquiz.com/gate-gate-cs-2005-question-58/
0

In following lecture Prof.  L. Sunil Chandran is teaching -  How maximal independent set and minimal vertex cover are related (Just check near around time 50:00 )?

Independent Set- a set of vertices in a graph no two of which are adjacent.

Maximal Independent set problem - Given a graph $G$, find the size of the maximal independent set in it. This problem in NP-hard.

Independent set decision problem - Given a graph $G$ and a number $k$, does $G$ have an independent set of size $k$. This problem is NP-complete (NP-hard but in NP).

Now, in the given problem  $\beta$ corresponds to the Independent set decision problem. But there is a difference there. We have $5$ instead of $k$. And this drastically changes the problem statement. We can now give a polynomial time deterministic algorithm for $\beta$.

• Find all vertex sets of size $5$. We get ${}^{|V|}C_5$ such vertex sets
• For each of them check if there is any adjacent vertices. This check can be done in constant time if we use an Adjacency matrix representation

Thus the whole time complexity reduces to ${}^{|V|}C_5$ which is $O\left({|V|}^5\right)$ and hence polynomial. $({}^{|V|}C_k$ is not polynomial but ${}^{|V|}C_5$ is $)$.

Problem $\alpha$ is asking for an independent set of size $|V| - 4$. This is equivalent to asking if $G$ has a vertex cover* of size $4$. Following a similar approach as done for $\beta$ this problem also can be done in polynomial time.

So, both $\alpha$ and $\beta$ are in $P$.

D choice.

Vertex cover of a graph $G$ is the set of vertices such that each edge of the graph is incident on atleast one of those vertices.

Independent Set and Vertex cover Reduction: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete.pdf

answered by Veteran (396k points)
edited by
+1
VcK is not polynomial but Vck is ! I think you meant Vc4 here :)
0
Arjun Sir ,  β is in P. But how can α be?"Problem α is asking for an independent set of size |V|−4 . This is equivalent to asking if G has a vertex cover of size 4." Sir how? vertex cover + independence no(ie the maxmimum independent set size possible)=|V| but here |V|−4 is not the independence no ,independence no can be more than this (finding independence no is NPH) . here it is the independent set decision problem ie we check if |V|−4 size indeendent set is present or not. so is n't it option B?Sir, please correct me ..
0

here |V|−4 is not the independence no ,independence no can be more than this

Then what is |V|-4?

0
independence no is the maximum independent set size of a graph, here it is just checked if any independent set of size |V|-4 exists or not, but does it mean this is the maximum independent set?Maximum independent set  finding is NPH problem not NP(you have also mentioned that ).
0
yes, it is not. I never used the "maximum". So, the question is if a graph has a vertex cover of $k$, can we say that it has an independent set (not necessarily maximum) of size $|V|-k$?
+1
okay Sir... now I have understood. :)
0
@arjun sir why not the same logic applicable for Vck as u applied for Vc5 ?

1
2