Consider the following two problems on undirected graphs α : Given G(V, E),…
2005
Consider the following two problems on undirected graphs
α : Given G(V, E), does G have an independent set of size | V | - 4?
β : Given G(V, E), does G have an independent set of size 5? Which one of the following is TRUE?
- A.
α is in P and β is NP-complete
- B.
α is NP-complete and β is in P
- C.
Both α and β are NP-complete
- D.
Both α and β are in P
Attempted by 99 students.
Show answer & explanation
Correct answer: D
Problem β asks if there is an independent set of size 5. Since the size k=5 is fixed, we can check all subsets of vertices of size 5 in O(n^5) time. This places β in P. Problem α asks if there is an independent set of size |V| - 4. This is equivalent to asking if there is a vertex cover of size 4 (since I + VC = V). Since the vertex cover size k=4 is fixed, we can check all subsets of vertices of size 4 in O(n^4) time. This places α in P. Therefore, both problems are solvable in polynomial time.
A video solution is available for this question — log in and enroll to watch it.