Problem (Bottleneck Path) Input: An edge-weighted undirected graph G and an integer k. Question: Does there exist a path such that the sum of the edge weights is at least k? Reduce the NP-hard problem...

Problem (Bottleneck Path)

Input: An edge-weighted undirected graph G and an integer k.

Question: Does there exist a path such that the sum of the edge weights is at least k?

Reduce the NP-hard problem Independent Set to show that the Bottleneck Path problem isNP-hard.