Approximation hardness of edge dominating set problems

Author: Chlebík Miroslav   Chlebíková Janka  

Publisher: Springer Publishing Company

ISSN: 1382-6905

Source: Journal of Combinatorial Optimization, Vol.11, Iss.3, 2006-05, pp. : 279-290

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.