Suppose that there is a polynomial time algorithm to decide Is there is a path P...

Transcribed Image Text:

Suppose that there is a polynomial time algorithm to decide "Is there is a path P that visits each vertex of the graph once where Ledge eep We W" for integer weights we and integer W. Devise a polynomial time algorithm which computes the minimal possible value for W for which there is a path visiting each vertex once where the sum of edge weights is W. Suppose that there is a polynomial time algorithm to decide "Is there is a path P that visits each vertex of the graph once where Ledge eep We W" for integer weights we and integer W. Devise a polynomial time algorithm which computes the minimal possible value for W for which there is a path visiting each vertex once where the sum of edge weights is W.