Answer to Question #38315 in Discrete Mathematics for Sujata Roy

Question

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

Answer 1

Both are in P

for α : there are C(V,V-4) = C(V,4) sets of size 4, we just need to verify whether one of these sets is independent, the time complexity for checking a set of size V-4 is independent or not.. can be done in V^2 time.. So for total C(V,4) = O(V^4) sets, the time complexity will be O(V^6).. which is polynomial

Similarly for β : there are C(V,5) sets of size 5, we just need to verify whether one of these sets is independent, the time complexity for checking a set of size 5 is independent or not.. can be done in constant time So for total C(V,5) = O(V^5) sets, the time complexity will be O(V^5).. which is polynomial