You, Alice and Bob are looking back on your notes and you want to know the...

 

Transcribed Image Text:

You, Alice and Bob are looking back on your notes and you want to know the complexity of a few graph problems. The two that you came across are the Shortest Path problem and the Travelling Salesperson Problem. Unfortunately they are still in their optimization problem form and you need to change them into decision problems to study their complexity. Shortest Path Input: G= (V,E, w) a weighted connected undirected graph, se V and dev Output: the length of the shortest path in G from s to d and a sequence of vertices V1, V2,..., Vk such that v =s, vkd, (vi, Vi+1) E E for all 1 You, Alice and Bob are looking back on your notes and you want to know the complexity of a few graph problems. The two that you came across are the Shortest Path problem and the Travelling Salesperson Problem. Unfortunately they are still in their optimization problem form and you need to change them into decision problems to study their complexity. Shortest Path Input: G= (V,E, w) a weighted connected undirected graph, se V and dev Output: the length of the shortest path in G from s to d and a sequence of vertices V1, V2,..., Vk such that v =s, vkd, (vi, Vi+1) E E for all 1