recategorized by
6,489 views
18 votes
18 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

recategorized by

1 Answer

Best answer
23 votes
23 votes

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

edited by
Answer:

Related questions

50 votes
50 votes
6 answers
2
31 votes
31 votes
2 answers
4
go_editor asked Nov 27, 2016
11,378 views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow numbe...