Please answer all the parts Check (circle) whichever applied to maximum independ

Question

Please answer all the parts Check (circle) whichever applied to maximum independent set graphs in a. NP-complete Yes No Don't know b. Solvable exactly in pt (polynomial time) Yes No Don't know c. Approximable in pt within factor 2.75 Yes No Don't know d. Approximable in pt within factor 1.9999 Yes No Don't know e. Approximable in pt within factor 1.4999 Yes No Don't know Check whichever applied to the traveling salesperson problem: a. NP-complete Yes No Don't know b. Solvable exactly in pt (polynomial time) c. Approximable in pt within factor 2.1666 Yes No Don't know d. Approximable in pt within factor 1.9999 Yes No Don't know e. Approximable in pt within factor 1.4999 Yes No Don't know Check whichever applied to the vertex cover problem (assuming P notequalto Np): a. NP-complete Yes No Don't know b. Solvable exactly in pt (polynomial time) No, Don't know c. Approximable in pt within factor 2.9999 Yes No Don't know d. Approximable in pt thin factor 2.3333 No Don't know e. Approximable in Yes in pt within factor 1.0001 Yes No Don't

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 P
• Subjects

---