Approximating Subdense Instances of Covering Problems

We study the approximability of subdense instances of various covering optimization problems, including Vertex Cover, Connected Vertex Cover, Set Cover, and Steiner Tree problems. In those instances, the minimum (or average) degree of the underlying graph is o(n), but Ω(n/ψ(n)) for some function ψ of the number n of vertices. We design new approximation algorithms or new polynomial time approximation schemes (PTAS) for those problems and establish the first approximation hardness results for some of them.