Approximation algorithms for partially covering with edges

The edge dominating set (EDS) and edge-cover (EC) problems are classical graph covering problems in which one seeks a minimum cost collection of edges which covers the edges or vertices, respectively, of a graph. We consider the generalized partial cover version of these problems, in which failing to cover an edge, in the EDS case, or vertex, in the EC case, induces a penalty. Given a bound on the total amount of penalties that we are permitted to pay, the objective is to find a minimum cost cover with respect to this bound. We give an 8/3-approximation for generalized partial EDS. This result matches the best-known guarantee for the { 0, 1 } -EDS problem, a specialization in which only a specified set of edges need to be covered. Moreover, 8/3 corresponds to the integrality gap of the natural formulation of the { 0, 1 } -EDS problem. Our techniques can also be used to derive an approximation scheme for the generalized partial edge-cover problem, which is NP -complete even though the uniform penalty version of the partial edge-cover problem is in P.

Authors

• Ojas Parekh

Keywords

• Edge dominating set
• Edge cover
• Partial cover
• Linear program
• Approximation algorithm