Abstract
An edge dominating set in a graph G = (V, E) is a subset S of edges such that each edge in E − S is adjacent to at least one edge in S. The edge dominating set problem, to find an edge dominating set of minimum size, is a basic and important NP-hard problem that has been extensively studied in approximation algorithms and parameterized complexity. In this paper, we present improved hardness results and parameterized approximation algorithms for edge dominating set. More precisely, we first show that it is NP-hard to approximate edge dominatingset in polynomial time within a factor better than 1.18. Next, we give a parameterized approximation schema (with respect to the standard parameter) for the problem and, finally, we develop an O ∗(1.821τ)-time exact algorithm where τ is the size of a minimum vertex cover of G.
Similar content being viewed by others
References
Binkele-Raible, D., Fernau, H.: Enumerate and measure: improving parameter budget management. In: Raman, V., Saurabh, S. (eds.) Proc. International Symposium on Parameterized and Exact Computation, IPEC’10, volume 6478 of Lecture Notes in Computer Science, pp 38–49. Springer-Verlag (2010)
Bourgeois, N., Escoffier, B., Paschos, V. Th.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954–1970 (2011)
Brankovic, L., Fernau, H.: A novel parameterised approximation algorithm for minimum vertex cover. Theor. Comput. Sci. 511, 85–108 (2013)
Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06, volume 4169 of Lecture Notes in Computer Science, pp 96–108. Springer-Verlag (2006)
Cardinal, J., Langerman, S., Levy, E.: Improved approximation bounds for edge dominating set in dense graphs. Theoret. Comput. Sci. 410(8-10), 949–957 (2009)
Carr, R., Fujito, T., Konjevod, G., Parekh, O.: A \((2+\frac {1}{10})\)-approximation algorithm for a generalization of the weighted edge-dominating set problem. J. Comb. Optim. 5, 317–326 (2001)
Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40-42), 3736–3756 (2010)
Chlebik, M., Chlebikova, J.: Approximation hardness of edge dominating set problems. J. Comb. Optim. 11(3), 279–290 (2006)
Dinur, I., Safra, M.: The importance of being biased. Proc. STOC’02, 33–42 (2002)
Downey, R.G., Fellows, M.R., McCartin, C., Rosamond, F.A.: Parameterized approximation of dominating set problems. Inform. Process. Lett. 109(1), 68–70 (2008)
Fellows, M.R., Kulik, A., Rosamond, F.A., Shachnai, H.: Parameterized approximation via fidelity preserving transformations. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) Proc. ICALP’12, volume 7391 of Lecture Notes in Computer Science, pp 351–362. Springer-Verlag (2012)
Fernau, H.: Edge dominating set: efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) Proc. International Workshop on Parameterized and Exact Computation, IWPEC’06, volume 4169 of Lecture Notes in Computer Science, pp 142–153. Springer-Verlag (2006)
Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181–207 (2009)
Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discret. Appl. Math. 118, 199–207 (2002)
Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 − ε. J. Comput. System Sci. 74(3), 335–349 (2008)
Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60–78 (2008)
Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theory Comput. Syst. 41(3), 563–587 (2007)
Schmied, R., Viehmann, C.: Approximating edge dominating set in dense graphs. Theoret. Comput. Sci. 414(1), 92–99 (2012)
van Rooij, J.M.M., Bodlaender, H.L.: Exact Algorithms for Edge Domination. Algorithmica 64(4), 535–563 (2012)
Xiao, M., Kloks, T., Poon, S.-H.: New parameterized algorithms for the edge dominating set problem. Theor. Comput. Sci. 511, 147–158 (2013)
Xiao, M., Nagamochi, H.: Parameterized edge dominating set in graphs with degree bounded by 3. Theor. Comput. Sci. 508, 2–15 (2013)
Xiao, M., Nagamochi, H.: A refined exact algorithm for edge dominating set. In: Agrawal, M., Barry Cooper, S., Li, A. (eds.) Proc. Theory and Applications of Models of Computation, TAMC’12, volume 7287 of Lecture Notes in Computer Science, pp 360–372. Springer-Verlag (2012)
Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. App. Math. 38(3), 364–372 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by the French Agency for Research under the DEFIS program TODO, ANR-09-EMER-010, the National Natural Science Foundation of China under the Grant 61370071 and Fundamental Research Funds for the Central Universities under the Grant ZYGX2012J069. An extended abstract of the paper appears in the proceedings of IPEC’12, LNCS, volume 7535
Rights and permissions
About this article
Cite this article
Escoffier, B., Monnot, J., Paschos, V.T. et al. New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set . Theory Comput Syst 56, 330–346 (2015). https://doi.org/10.1007/s00224-014-9549-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-014-9549-5