I'm attending a master course in Algorithm for Bioinformatics, and I'm trying to solve some exercise in order to pass the exam. I'm stuck in this problem and I don't understand in which way I have to solve it. Could you help? Thanks the next few lines are the exercise:
Argue whether you believe that the following problem has a polynomial time algorithm Input: A complete undirected graph G with non-negative weights on the edges, and a weight bound W. Solution: A simple path with the maximum possible number of vertices among all paths in G of weight < W.
This is NP-Hard, and thus there is no known polynomial solution to it.
It is easy to reduce this problem from the Hamiltonian Path problem1.
Given a graph G=(V, E), create:
G' = (V, E', w)
Where:
E' = VxV (all edges)
w(u,v) = 1 if (u,v) is in E
2 otherwise
Now, G' has a valid solution with |V| maximal weight if and only if G is hamiltonian.
(->) If 'G' is hamiltonian, then there is a path v1->v2->...->vn. Weights of all these edges is 1, so total weight in G' is |V|-1, making it maximal and valid.
(<-) If there is a path in G' with value<|V|, and we know it is maximal - so if it goes through all vertices - it cannot have edges with w(u,v)=2 (otherwise it will exceed the maximal weight). Then, this path is hamiltonian in G.
(1) A hamiltonian path is a simple path that goes through all vertices in the graph. If a graph has such a path, we call it a hamiltonian graph. The Hamiltonian Path Problem is finding if a graph is hamiltonian or not.