Algorithmic aspects of upper edge domination. (English) Zbl 1516.68070
Summary: We study the problem of finding a minimal edge dominating set of maximum size in a given graph \(G = (V, E)\), called Upper EDS. We show that this problem is not approximable within a ratio of \(n^{\varepsilon - \frac{ 1}{ 2}} \), for any \(\varepsilon \in(0, \frac{ 1}{ 2})\), assuming \(\mathsf{P} \neq \mathsf{NP} \), where \(n = | V |\). On the other hand, for graphs of minimum degree at least 2, we give an approximation algorithm with ratio \(\frac{ 1}{ \sqrt{ n}} \), matching this lower bound. We further show that Upper EDS is \(\mathsf{APX} \)-complete in bipartite graphs of maximum degree 4, and \(\mathsf{NP} \)-hard in planar bipartite graphs of maximum degree 4.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
References:
| [1] | AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim V.; Monnot, Jérôme; Ries, Bernard, A dichotomy for upper domination in monogenic classes, (Proceedings of COCOA 2014: the 8th International Conference on Combinatorial Optimization and Applications. Proceedings of COCOA 2014: the 8th International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol. 8881 (2014), Springer), 258-267 · Zbl 1391.05240 |
| [2] | AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim V.; Monnot, Jérôme; Ries, Bernard; Zamaraev, Victor, A boundary property for upper domination, (Proceedings of IWOCA 2016: the 27th International Workshop on Combinatorial Algorithms. Proceedings of IWOCA 2016: the 27th International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science, vol. 9843 (2016), Springer), 229-240 · Zbl 1392.68195 |
| [3] | AbouEisha, Hassan; Hussain, Shahid; Lozin, Vadim V.; Monnot, Jérôme; Ries, Bernard; Zamaraev, Viktor, Upper domination: towards a dichotomy through boundary properties, Algorithmica, 80, 10, 2799-2817 (2018) · Zbl 1391.05241 |
| [4] | Alimonti, Paola; Kann, Viggo, Some APX-completeness results for cubic graphs, Theor. Comput. Sci., 237, 1-2, 123-134 (2000) · Zbl 0939.68052 |
| [5] | Ausiello, Giorgio; Marchetti-Spaccamela, Alberto; Crescenzi, Pierluigi; Gambosi, Giorgio; Protasi, Marco; Kann, Viggo, Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties (1999), Springer · Zbl 0937.68002 |
| [6] | Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, Discrete Appl. Math., 280, 23-42 (2020) · Zbl 1439.05174 |
| [7] | Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th., Algorithmic aspects of upper domination: a parameterised perspective, (Proceedings of AAIM 2016: the 11th International Conference on Algorithmic Aspects in Information and Management. Proceedings of AAIM 2016: the 11th International Conference on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, vol. 9778 (2016), Springer), 113-124 · Zbl 1476.68114 |
| [8] | Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th., Upper domination: complexity and approximation, (Proceedings of IWOCA 2016: the 27th International Workshop on Combinatorial Algorithms. Proceedings of IWOCA 2016: the 27th International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science, vol. 9843 (2016), Springer), 241-252 · Zbl 1478.68099 |
| [9] | Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérome; Paschos, Vangelis Th., The many facets of upper domination, Theor. Comput. Sci., 717, 2-25 (2018) · Zbl 1388.68099 |
| [10] | Cheston, Grant A.; Fricke, Gerd; Hedetniemi, Stephen T.; Jacobs, David Pokrass, On the computational complexity of upper fractional domination, Discrete Appl. Math., 27, 3, 195-207 (1990) · Zbl 0717.05068 |
| [11] | Chlebík, Miroslav; Chlebíková, Janka, Approximation hardness of edge dominating set problems, J. Comb. Optim., 11, 3, 279-290 (2006) · Zbl 1255.90121 |
| [12] | Chlebík, Miroslav; Chlebíková, Janka, Complexity of approximating bounded variants of optimization problems, Theor. Comput. Sci., 354, 3, 320-338 (2006) · Zbl 1105.90110 |
| [13] | Cockayne, Ernest J.; Favaron, Odile; Payan, C.; Thomason, A. G., Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math., 33, 3, 249-258 (1981) · Zbl 0471.05051 |
| [14] | Edmonds, Jack, Paths, trees and flowers, Can. J. Math., 17, 449-467 (1965) · Zbl 0132.20903 |
| [15] | Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis Th.; Xiao, Mingyu, New results on polynomial inapproximability and fixed parameter approximability of edge dominating set, Theory Comput. Syst., 56, 2, 330-346 (2015) · Zbl 1328.68090 |
| [16] | Fellows, Michael R.; Fricke, Gerd; Hedetniemi, Stephen T.; Jacobs, David P., The private neighbor cube, SIAM J. Discrete Math., 7, 1, 41-47 (1994) · Zbl 0795.05078 |
| [17] | Garey, Michael R.; Johnson, David S., The rectilinear steiner tree problem is NP-complete, SIAM J. Appl. Math., 32, 826-834 (1977) · Zbl 0396.05009 |
| [18] | Michael R. Garey, David S. Johnson, 1978, Unpublished result. |
| [19] | Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman & Co.: W.H. Freeman & Co. New York, NY, USA · Zbl 0411.68039 |
| [20] | Garey, Michael R.; Johnson, David S.; Stockmeyer, Larry J., Some simplified NP-complete graph problems, Theor. Comput. Sci., 1, 3, 237-267 (1976) · Zbl 0338.05120 |
| [21] | Golovach, Petr A.; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve, An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Algorithmica, 72, 3, 836-859 (2015) · Zbl 1330.05118 |
| [22] | Harutyunyan Mehdi Khosravian Ghadikolaei, Ararat; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris, On the complexity of the upper r-tolerant edge cover problem, (Proceedings of TTCS 2020: the 3rd IFIP WG 1.8 International Conference on Topics in Theoretical Computer Science. Proceedings of TTCS 2020: the 3rd IFIP WG 1.8 International Conference on Topics in Theoretical Computer Science, Lecture Notes in Computer Science, vol. 12281 (2020), Springer), 32-47 · Zbl 07316481 |
| [23] | (Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J., Domination in Graphs: Advanced Topics (1998), Marcel Dekker) · Zbl 0883.00011 |
| [24] | Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J., Fundamentals of Domination in Graphs (1998), Marcel Dekker · Zbl 0890.05002 |
| [25] | Horton, Joseph Douglas; Kilakos, Kyriakos, Minimum edge dominating sets, SIAM J. Discrete Math., 6, 3, 375-387 (1993) · Zbl 0782.05083 |
| [26] | Jacobson, Michael S.; Peters, Ken, Chordal graphs and upper irredundance, upper domination and independence, Discrete Math., 86, 59-69 (1990) · Zbl 0744.05063 |
| [27] | Johnson, David S., Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci., 9, 3, 256-278 (1974) · Zbl 0296.65036 |
| [28] | Khoshkhah Mehdi Khosravian Ghadikolaei, Kaveh; Monnot, Jérôme; Sikora, Florian, Weighted upper edge cover: complexity and approximability, (Proceedings of WALCOM 2019: the 13th International Conference on Algorithms and Computation. Proceedings of WALCOM 2019: the 13th International Conference on Algorithms and Computation, Lecture Notes in Computer Science, vol. 11355 (2019), Springer), 235-247 · Zbl 1420.68093 |
| [29] | Khoshkhah Mehdi Khosravian Ghadikolaei, Kaveh; Monnot, Jérôme; Sikora, Florian, Weighted upper edge cover: complexity and approximability, J. Graph Algorithms Appl., 24, 2, 65-88 (2020) · Zbl 1433.05261 |
| [30] | Kikuno, Tohru; Yoshida, Noriyoshi; Kakuda, Yoshiaki, The NP-completeness of the dominating set problem in cubic planar graphs, Trans. Inst. Electron. Commun. Eng. Jpn., Sect. E, 63, 6, 443-444 (1980) · Zbl 0452.90025 |
| [31] | Korte, Bernhard; Hausmann, Dirk, An Analysis of the Greedy Heuristic for Independence Systems, In Annals of Discrete Mathematics, vol. 2, 65-74 (1978), North-Holland · Zbl 0392.90058 |
| [32] | Manlove, David F., Minimaximal and maximinimal optimisation problems: a partial order-based approach (1998), University of Glasgow, Computing Science, PhD thesis |
| [33] | McRae, Alice A., Generalizing NP-completeness proofs for bipartite and chordal graphs (1994), Clemson University, Department of Computer Science, South Carolina, PhD thesis |
| [34] | Papadimitriou, Christos H.; Yannakakis, Mihalis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43, 3, 425-440 (1991) · Zbl 0765.68036 |
| [35] | Raz, Ran; Safra, Shmuel, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, (Proceedings of STOC 1997: the 29th Annual ACM Symposium on Theory of Computing (1997), ACM: ACM New York, NY, USA), 475-484 · Zbl 0963.68175 |
| [36] | Schmied, Richard; Viehmann, Claus, Approximating edge dominating set in dense graphs, Theor. Comput. Sci., 414, 1, 92-99 (2012) · Zbl 1235.68079 |
| [37] | Trevisan, Luca, Non-approximability results for optimization problems on bounded degree instances, (Proceedings of STOC 2001: the 33rd Annual ACM Symposium on Theory of Computing (2001)), 453-461 · Zbl 1323.90059 |
| [38] | Yannakakis, Mihalis; Gavril, Fanica, Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 3, 364-372 (1980) · Zbl 0455.05047 |
| [39] | Zuckerman, David, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput., 3, 1, 103-128 (2007) · Zbl 1213.68322 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
