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.

CodePudding user response：

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 problem¹.

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.