IIT Madras MS written test 2019 - Algorithms - 1

Question

Let SP be the problem of finding the shortest path between 2 nodes, and LP be the problem of finding the longest path between 2 nodes, in an unweighted, undirected graph. Which of the following is true?

• A. SP is NP-hard, LP is not
• B. LP is NP-hard, SP is not
• C. Both are NP-hard
• D. Neither SP nor LP is NP-hard

Comments

as all NPC are NPH and It's already mentioned undirected graph.See this.

---

@Abhisek Tiwari 4

yes, they mention longest path as NP-Hard, but shortest path they havenot mentioned 

right?

---

shortest path is standard eg of NPC. As NPC is subset of NPH So can't we say All NPC are NPH also?