We define the decision version of the Shortest Path problem as follows: given an undirected graph...

Transcribed Image Text:

We define the decision version of the Shortest Path problem as follows: given an undirected graph G = (V, E), two distinct vertices s, t€ V, and a positive integer k, return yes if and only if there exists a path from s to t of length at most k. Otherwise, return no. For each of the two questions below, decide whether the answer is (i) "Yes", (ii) "No", or (iii) "Unknown, because it would resolve the question of whether P-NP." Give an explanation of your answers. 1. Question: (11 points) Is it the case that Shortest Path ≤p Independent Set? 2. Question: (11 points) Is it the case that Independent Set <p Shortest Path? We define the decision version of the Shortest Path problem as follows: given an undirected graph G = (V, E), two distinct vertices s, t€ V, and a positive integer k, return yes if and only if there exists a path from s to t of length at most k. Otherwise, return no. For each of the two questions below, decide whether the answer is (i) "Yes", (ii) "No", or (iii) "Unknown, because it would resolve the question of whether P-NP." Give an explanation of your answers. 1. Question: (11 points) Is it the case that Shortest Path ≤p Independent Set? 2. Question: (11 points) Is it the case that Independent Set <p Shortest Path?

Answer rating: 100% (QA)

This question is asking about the relationship between two wellknown problems in computational complexity the Shortest Path problem and the Independen... View the full answer