𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation hardness of edge dominating set problems

✍ Scribed by Miroslav Chlebík; Janka Chlebíková

Publisher
Springer US
Year
2006
Tongue
English
Weight
324 KB
Volume
11
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Near-optimal hardness results and approx
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
✍ Venkatesan Guruswami; Sanjeev Khanna; Rajmohan Rajaraman; Bruce Shepherd; Mihali 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 308 KB

We study the approximability of edge-disjoint paths and related problems. In the edge-disjoint paths (EDP) problem, we are given a network G with source-sink pairs ðs i ; t i Þ; 1pipk; and the goal is to find a largest subset of source-sink pairs that can be simultaneously connected in an edge-disjo