Differential approximation for optimal satisfiability and related problems

We study the differential approximability of several optimization satisfiability problems. We prove that, unless co-RP=NP, MIN SAT is not differential 1/m^1-ϵ-approximable for any ϵ>0, where m is the number of clauses. We also prove that any differential approximation algorithm for MAX minimal vertex cover can be transformed into a differential approximation algorithm for MIN kSAT achieving the same differential performance ratio. This leads us to study the differential approximability of MAX minimal vertex cover and MIN independent dominating set. Both of them are equivalent for the differential approximation. For these problems we prove a strong inapproximability result, informally, unless P=NP, any approximation algorithm has worst-case approximation ratio equal to 0.