Edge dominating and hypomatchable sets
Ojas Parekh · 2002
The weighted edge dominating set problem (EDS) generalizes both the weighted vertex cover problem and the problem of covering the edges of graph by a minimum cost set of both vertices and edges. Although EDS was proven NP-complete in 1980, not much progress had been made in improving its approximability to match that of weighted vertex cover until 2000. In this paper we develop a 2-approximation for weighted EDS by honing the technique of a recent 2 1/10-approximation which exploits the close polyhedral relationship between EDS and the edge cover problem. For the sake of completeness we also present a new direct proof of Edmonds and Johnson's characterization of the edge cover polyhedron. Our approximation guarantee is tight in the sense that the existence of a (2-e)-approximation for weighted EDS for some constant, e would imply a (2-e)-approximation for weighted vertex cover, constituting a major breakthrough in the field.