Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  Which of the following is not an example of a... Start Learning for Free
Which of the following is not an example of an NP-hard problem?
  • a)
    Scheduling identical processor
  • b)
    Traveling salesman problem
  • c)
    Node cover decision problem
  • d)
    2-Coloring of graph
Correct answer is option 'D'. Can you explain this answer?
Most Upvoted Answer
Which of the following is not an example of an NP-hard problem?a)Sched...
There is a polynomial time algorithm for 2-coloring. It is computationally hard to color a graph. 2-colored graph is also known as bipartite graph, and to color all the nodes of a bipartite graph, we have to use BFS technique.
Start with the vertex v, then go to all the neighbors and then to all the unvisited neighbors of that node and so on by stroring the current wave-front in a queue. There can be multiple BFS trees for a single 2-colorable graph. It is the property of NP-complete problems that if there is a polynomial time algorithm for any of them, then there will be a polynomial time algorithm for all of them.
Thus, 2-coloring of graph is an NP-complete problem and not an NP-hard problem.
Free Test
Community Answer
Which of the following is not an example of an NP-hard problem?a)Sched...
Introduction:
NP-hard is a classification in the field of computer science that refers to a set of problems that are at least as hard as the hardest problems in the complexity class NP (nondeterministic polynomial time). These problems are difficult to solve efficiently, and finding an optimal solution may require significant computational resources.

Explanation:
To determine which of the given options is not an example of an NP-hard problem, let's analyze each option:

a) Scheduling identical processor:
Scheduling identical processors refers to assigning tasks to a set of identical processors in order to optimize certain criteria such as minimizing the total completion time or maximizing the throughput. This problem is known as the identical parallel machine scheduling problem and is NP-hard. Therefore, option 'a' is an example of an NP-hard problem.

b) Traveling salesman problem:
The traveling salesman problem (TSP) is a classic optimization problem where the goal is to find the shortest possible route that allows a salesman to visit a set of cities and return to the starting city, visiting each city exactly once. It is a well-known NP-hard problem and is often used as a benchmark for testing optimization algorithms. Therefore, option 'b' is an example of an NP-hard problem.

c) Node cover decision problem:
The node cover decision problem involves finding the minimum number of nodes in a graph that can cover all the edges. This problem is known to be NP-hard, as it can be reduced to the vertex cover problem, which is a classic NP-hard problem. Therefore, option 'c' is an example of an NP-hard problem.

d) 2-Coloring of graph:
The 2-coloring of a graph problem involves assigning one of two colors to each vertex of a graph such that no adjacent vertices have the same color. This problem is known as the graph coloring problem and is NP-hard. Therefore, option 'd' is not the correct answer.

Conclusion:
Based on the analysis, option 'd' is not the correct answer as it represents a problem that is NP-hard. The correct answer should be one of the other options (a, b, or c) which are all examples of NP-hard problems.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Question Description
Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2025 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer?.
Solutions for Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer?, a detailed solution for Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? has been provided alongside types of Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice Which of the following is not an example of an NP-hard problem?a)Scheduling identical processorb)Traveling salesman problemc)Node cover decision problemd)2-Coloring of graphCorrect answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev