The Gateway to Computer Science Excellence
+12 votes

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

in Theory of Computation by Veteran (52.2k points)
recategorized by | 1.4k views
That's the same question from me, WHY? Who told it is NPC?
Sir ,answ was given NPC on the below link :
Additional information.

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 )?

1 Answer

+15 votes
Best answer

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:

by Veteran (432k points)
edited by
VcK is not polynomial but Vck is ! I think you meant Vc4 here :)
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 ..

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

Then what is |V|-4?

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 ).
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$?
okay Sir... now I have understood. :)
@arjun sir why not the same logic applicable for Vck as u applied for Vc5 ?

@Arjun sir, How is the β problem different from independent set decision problem? Is k not constant there?


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,388 answers
105,416 users