Discussion
For the following statements of problems :
(I) 3 COL : Given a graph G, can be painted with 3 colours.
(II) COLO : given a graph G, find the chromatic number of G.
Select the correct answer :
Answer: C
The answer is (I) is NP-complete & (II) is NP-hard.
3 COL asks a yes/no question: can the graph be coloured with 3 colours? It is in NP, because a proposed colouring can be checked in polynomial time, and it is one of Karp's classic NP-complete problems.
COLO asks for the chromatic number itself, an optimisation problem rather than a decision problem. Solving it would also solve 3 COL, so it is NP-hard, but it is not in NP as stated. Neither problem is known to be solvable in polynomial time, so the options calling either one polynomial are wrong, and 'Only (I) is NP-complete' leaves out the classification of (II).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development