DSA - Graphs and Hashing -Q2

Question

Let be a connected, undirected graph, and let a and b be two distinct vertices in V. Let be the problem of finding a shortest simple path between a and b, and let be the problem of finding a longest simple path between a and b.

Which of the following statements about and is true?

(A) Both and can be solved in polynomial time.

(B) can be solved in polynomial time but is not known to be solvable in polynomial time.

(C) is not known to be solvable in polynomial time but can be solved in polynomial time.

(D) It is not known whether either or can be solved in polynomial time.

Answer 1

The longest path problem for a general graph is not as easy as the shortest path problem because the longest path problem doesn’t have optimal substructure property. In fact, the Longest Path problem is NP-Hard for a general graph.

https://www.quora.com/Why-is-the-longest-path-problem-NP-complete-given-that-the-shortest-path-problem-is-not-NP-complete

Comments

It would be better if in Answer you tell why it is NP hard. :)

We all know P1 is nlogn.
But P2 is NP complete.
Given a solution, you can verify it. But it is not NP hard bro.

---

Every NP complete is NP hard.
And telling why a problem is NP hard would take around 8-10 pages of answer.
This question could be skipped as well as NP complexity is not in syllabus.