Approximation hardness of minimum edge dominating set and minimum maximal matching

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

194 Downloads (Pure)


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 76 . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.
Original languageEnglish
Title of host publicationAlgorithms and computation
Subtitle of host publication14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings
EditorsToshihide Ibaraki, Naoki Katoh, Hirotaka Ono
Place of PublicationBerlin
ISBN (Electronic)9783540245872
ISBN (Print)9783540206958
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • minimum edge dominating set
  • minimum maximal matching
  • approximation lower bound
  • bounded degree graphs
  • everywhere dense graphs


Dive into the research topics of 'Approximation hardness of minimum edge dominating set and minimum maximal matching'. Together they form a unique fingerprint.

Cite this