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 7/6. The result extends with
negligible
loss to bounded degree graphs and to everywhere
dense graphs.
| Original language | English |
|---|---|
| Pages (from-to) | 279--290 |
| Journal | Journal of Combinatorial Optimisation |
| Volume | 11 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - May 2006 |
Keywords
- minimum edge dominating set
- minimum maximal matching
- approximation lower bound
- bounded degree graphs
- everywhere dense graphs