Abstract
We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple 2 1/10-approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2r WVC, where r WVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of r WVC currently stands at \( 2 - \frac{{\log {\mathbf{ }}\log {\mathbf{ }}|V|}} {{2{\mathbf{ }}\log {\mathbf{ }}|V|}} \cdot \) . Furthermore we establish that the factor of 2 1/10 is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem.
Work supported in part by the United States Department of Energy under contract DE-AC04-94AL85000.
{emfujito@nuee.nagoya-u.ac.jp}
Supported in part by an NSF CAREER Grant CCR-9625297.
{emod@andrew.cmu.edu}
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the 33rdAnnual IEEE Symposium on Foundations of Computer Science, pages 14–23, 1992.
B. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41:153–180, 1994.
V. Chvátal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3):233–235, 1979.
J. Edmonds and E. Johnson. Matching, a well solved class of integer linear programs. In Combinatorial Structures and Their Applications, pages 89–92. Gordon & Breach, New York, 1970.
U. Feige. A threshold of ln n for approximating set cover. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 314–318, May 1996.
M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.
F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1969.
D.S. Hochbaum, editor. Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston, MA, 1997.
J. Horton and K. Kilakos. Minimum edge dominating sets. SIAM J. Discrete Math., 6(3):375–387, 1993.
H. Hunt III, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, and R. Stearns. A unified approach to approximation schemes for NP-and PSPACE-hard problems for geometric graphs. In Proc. 2nd Ann. European Symp. on Algorithms, pages 424–435, 1994.
D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256–278, 1974.
L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Math., 13:383–390, 1975.
S. Mitchell and S. Hedetniemi. Edge domination in trees. In Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pages 489–509, 1977.
K. G. Murty and C. Perin. A 1-matching blossom-type algorithm for edge covering problems. Networks, 12:379–391, 1982.
C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. J. Comput. System Sci., 43:425–440, 1991.
W. R. Pulleyblank. Matchings and extensions. In Handbook of combinatorics, volume 1, pages 179–232. Elsevier, 1995.
A. Srinivasan, K. Madhukar, P. Nagavamsi, C. P. Rangan, and M.-S. Chang. Edge domination on bipartite permutation graphs and cotriangulated graphs. Information Processing Letters, 56:165–171, 1995.
M. Yannakakis and F. Gavril. Edge dominating sets in graphs. SIAM J. Appl. Math., 38(3):364–372, 1980.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carr, R., Fujito, T., Konjevod, G., Parekh, O. (2000). A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem. In: Paterson, M.S. (eds) Algorithms - ESA 2000. ESA 2000. Lecture Notes in Computer Science, vol 1879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45253-2_13
Download citation
DOI: https://doi.org/10.1007/3-540-45253-2_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41004-1
Online ISBN: 978-3-540-45253-9
eBook Packages: Springer Book Archive