nach oben

Theory of Computing Systems

Erschienen in:

01.02.2015

New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set

verfasst von: Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao

Erschienen in: Theory of Computing Systems | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Rent or Buy Problems with a Fixed Time Horizon

Nächster Artikel Estimating the Volume of Solution Space for Satisfiability Modulo Linear Real Arithmetic

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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)MATHMathSciNet

Brankovic, L., Fernau, H.: A novel parameterised approximation algorithm for minimum vertex cover. Theor. Comput. Sci. 511, 85–108 (2013)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

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)CrossRefMATHMathSciNet

Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40-42), 3736–3756 (2010)CrossRefMATHMathSciNet

Chlebik, M., Chlebikova, J.: Approximation hardness of edge dominating set problems. J. Comb. Optim. 11(3), 279–290 (2006)CrossRefMATHMathSciNet

Dinur, I., Safra, M.: The importance of being biased. Proc. STOC’02, 33–42 (2002)

10.

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)CrossRefMathSciNet

11.

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)

12.

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)

13.

Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181–207 (2009)CrossRefMATHMathSciNet

14.

Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discret. Appl. Math. 118, 199–207 (2002)CrossRefMATHMathSciNet

15.

Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)MATH

16.

Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 − ε. J. Comput. System Sci. 74(3), 335–349 (2008)CrossRefMATHMathSciNet

17.

Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60–78 (2008)CrossRef

18.

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)CrossRefMATHMathSciNet

19.

Schmied, R., Viehmann, C.: Approximating edge dominating set in dense graphs. Theoret. Comput. Sci. 414(1), 92–99 (2012)CrossRefMATHMathSciNet

20.

van Rooij, J.M.M., Bodlaender, H.L.: Exact Algorithms for Edge Domination. Algorithmica 64(4), 535–563 (2012)CrossRefMATHMathSciNet

21.

Xiao, M., Kloks, T., Poon, S.-H.: New parameterized algorithms for the edge dominating set problem. Theor. Comput. Sci. 511, 147–158 (2013)CrossRefMATHMathSciNet

22.

Xiao, M., Nagamochi, H.: Parameterized edge dominating set in graphs with degree bounded by 3. Theor. Comput. Sci. 508, 2–15 (2013)CrossRefMATHMathSciNet

23.

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)

24.

Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. App. Math. 38(3), 364–372 (1980)CrossRefMATHMathSciNet

Titel: New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set
verfasst von: Bruno Escoffier
Jérôme Monnot
Vangelis Th. Paschos
Mingyu Xiao
Publikationsdatum: 01.02.2015
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2015
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9549-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2015

Hardness of Approximation for Knapsack Problems

Topological Approach to Multivalued Information System

Estimating the Volume of Solution Space for Satisfiability Modulo Linear Real Arithmetic

On the Turing Completeness of the Semantic Web

Rent or Buy Problems with a Fixed Time Horizon

Sitting Closer to Friends than Enemies, Revisited