Check (circle) whichever applied to maximum independent set in graphs: a. NP-com

Question

Check (circle) whichever applied to maximum independent set in graphs: a. NP-complete b. Solvable exactly in pt (polynomial time) c. Approximable in pt within factor 2.9999 d. Approximable in pt within factor 1.9999 e. Approximable in pt within factor 1.4999 Check whichever applied to the traveling salesperson problem: a. NP-complete b. Solvable exactly in pt (polynomial time) c. Approximable in pt within factor 2.9999 Approximable in pt within factor 1.9999 e. Approximable in pt within factor 1.4999 Check whichever applied to the vertex cover problem (assuming P notequalto NP): a. NP-complete b. Solvable exactly in pt (polynomial time) b. Approximable in pt within factor 2.9999 d. Approximable in pt within factor 1.9999 e. Approximable in pt within factor 2.0001

Explanation / Answer

1)

Maximum independent set in graph

NP complete - YES

solved in pt - YES

2) Travelling salesman problem

NP complete - NO

solved in PT - NO

3) vertex cover problem( P is not equal to NP)

NP complete - YES

solved in pt -    there is no polynomial time solution for this unless P = NP

but here P is not Equals to NP then it cant be approxible in PT

so answer is NO

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---