I think that Minimum weight vertex cover problem is NP-easy. However I don't know how to prove that. Does anyone know how to prove it?



Is minimum weight vertex cover problem NP-easy?
Consider the following decision problem:



> 
> Given a vertex-weighted graph $G$, a subset $S$ of its vertices, and a number $k$, is there a vertex cover of $G$ extending $S$ with total weight at most $k$?
> 
> 
> 


This problem is clearly in NP. Let us see how to solve the minimum weight vertex cover problem using it as an oracle.


First, we find the least possible total weight of a vertex cover. This can be done using a bisection method, by repeatedly querying with $S=\varnothing$ and using varying $k$, starting with the sum of weights of all vertices (say). Call this minimal possible value $k\_0$.


Now querying the oracle on $G,k\_0$ and some set $S$ tells us whether there is a minimal weight cover containing the subset $S$, which lets us build a minimum weight cover inductively: first let $S$ range over all $1$-element subsets of vertices. After we find one which works, say $S=\{u\_1\}$, run the oracle for all subsets of the form $\{u\_1,u\_2\}$, and so on. After a number of queries at most quadratic in the number of vertices, we find a minimum weight vertex cover of $G$.


