Yes. A maximal value of k can be calculated as (largest weight in the graph) times (number of nodes in the graph). At that point you can do binary search to fin

Yes. A maximal value of k can be calculated as (largest weight in the graph) times (number of nodes in the graph). At that point you can do binary search to find the smallest k for which a solution exists. Under the assumption that the <= question can be answered in polynomial time, this entire algorithm will also complete in polynomial time.