C.Both are NP hard.

The Gateway to Computer Science Excellence

0 votes

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?

- SP is NP-hard, LP is not
- LP is NP-hard, SP is not
- Both are NP-hard
- Neither SP nor LP is NP-hard

52,223 questions

59,811 answers

201,020 comments

118,087 users