The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
102 views

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?

  1. SP is NP-hard, LP is not
  2. LP is NP-hard, SP is not
  3. Both are NP-hard
  4. Neither SP nor LP is NP-hard
in Algorithms by Junior (643 points) | 102 views
0
C.Both are NP hard.
0
How do u know, it will be Np-Hard?
0

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

0

@Abhisek Tiwari 4

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

right?

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

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,743 answers
192,225 comments
90,494 users