CSCE 310 Assignment 4 Summer 2018 1. 10 points Let G (V, E) be an undirected gra
ID: 3914813 • Letter: C
Question
CSCE 310 Assignment 4 Summer 2018 1. 10 points Let G (V, E) be an undirected graph. Given two vertices, u, vE V it is easy to determine the length of the shortest path between them using Dijkstra's algorithm. However, determining the longest path between u, v is NP-complete. Prove this as follows: assume that a "free" algorithm A exists for the longest path problem (it takes as input, G, u, v and outputs the length k of the longest path between u and v) and use it to design a polynomial time algorithm to solve the Hamiltonian Path problem, a known NP-complete problem.Explanation / Answer
For every permutation {v1, ..., vN} you check if you can get from v1 to v2, then from v2 to v3 etc. If you can, add corresponding edge length to the current path length. If not, go to the next permutation.
where
Time complexity is horrible O(N * N^N).
So, we can see from above we are trying to visit all the vertices of a Graph G from a starting vertex u untill we cover all the remaining vertices v. In this way we will cover Maximum path in the Graph G and we can find the Longest Path in G. This problem is very much similiar to Hamiltonian Path Problem, which itself is NP-Complete. Because out given problem also reduces to HAM-PATH problem, hence we can say that the Longest Path Problem is also NP-Complete. [Proved!]
Please let me know in case of any clarifications required. Thanks!