Answer to Question #38315 in Discrete Mathematics for Sujata Roy

Question #38315
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
1
Expert's answer
2014-01-14T02:49:02-0500
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

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS