Abstract
We consider Upper Domination, the problem of finding a maximum cardinality minimal dominating set in a graph. We show that this problem does not admit an \(n^{1-\epsilon }\) approximation for any \(\epsilon >0\), making it significantly harder than Dominating Set, while it remains hard even on severely restricted special cases, such as cubic graphs (APX-hard), and planar subcubic graphs (NP-hard). We complement our negative results by showing that the problem admits an \(O(\varDelta )\) approximation on graphs of maximum degree \(\varDelta \), as well as an EPTAS on planar graphs. Along the way, we also derive essentially tight \(n^{1-\frac{1}{d}}\) upper and lower bounds on the approximability of the related problem Maximum Minimal Hitting Set on d-uniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B.: A dichotomy for upper domination in monogenic classes. In: Zhang, Z., Wu, L., Xu, W., Du, D.-Z. (eds.) COCOA 2014. LNCS, vol. 8881, pp. 258–267. Springer, Heidelberg (2014)
Arkin, E.M., Bender, M.A., Mitchell, J.S.B., Skiena, S.: The lazy bureaucrat scheduling problem. Inf. Comput. 184(1), 129–146 (2003)
Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 153–180 (1994)
Bender, M.A., Clifford, R., Tsichlas, K.: Scheduling algorithms for procrastinators. J. Sched. 11(2), 95–104 (2008)
Berman, P., Fujito, T.: On the approximation properties of independent set problem in degree 3 graphs. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 449–460. Springer, Heidelberg (1995)
Bodlaender, H.L.: A partial \(k\)-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)
Boria, N., Della Croce, F.D., Paschos, V.T.: On the max min vertex cover Problem. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 37–48. Springer, Heidelberg (2014)
Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive boolean functions. Optim. Methods Softw. 10(2), 147–156 (1998)
Bourgeois, N., Escoffier, B., Paschos, V.T.: Fast algorithms for min independent dominating set. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol. 6058, pp. 247–261. Springer, Heidelberg (2010)
Bourgeois, N., Croce, F.D., Escoffier, B., Paschos, V.T.: Fast algorithms for min independent dominating set. Discrete Appl. Math. 161(4–5), 558–572 (2013)
Cheston, G., Fricke, G., Hedetniemi, S., Jacobs, D.: On the computational complexity of upper fractional domination. Discrete Appl. Math. 27(3), 195–207 (1990)
Cockayne, E.J., Favaron, O., Payan, C., Thomason, A.G.: Contributions to the theory of domination, independence and irredundance in graphs. Discrete Math. 33(3), 249–258 (1981)
Courcelle, B., Makowsky, A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theo. Comp. Syst. 33(2), 125–150 (2000)
Halldórsson, M.M.: Approximating the minimum maximal independence number. Inf. Process. Lett. 46(4), 169–172 (1993)
Hare, E.O., Hedetniemi, S.T., Laskar, R.C., Peters, K., Wimer, T.: Linear-time computability of combinatorial problems on generalized-series-parallel graphs. In: Johnson, D.S., et al. (eds.) Discrete Algorithms and Complexity (AP NY) (1987)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker, New York (1998)
Henning, M.A., Slater, P.J.: Inequalities relating domination parameters in cubic graphs. Discrete Math. 158(1–3), 87–98 (1996)
Håstad, J.: Clique is hard to approximate within \(n^{1-\epsilon }\). Acta Math. 182, 105–142 (1999)
Hurink, J., Nieberg, T.: Approximating minimum independent dominating sets in wireless networks. Inf. Process. Lett. 109(2), 155–160 (2008)
Jacobson, M.S., Peters, K.: Chordal graphs and upper irredundance, upper domination and independence. Discrete Math. 86(1–3), 59–69 (1990)
Kanté, M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Disc. Math. 28(4), 1916–1929 (2014)
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 446–457. Springer, Heidelberg (2015)
Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52, 233–252 (1994)
Lovász, L.: Three short proofs in graph theory. J. Combin. Theory Ser. B 19, 269–271 (1975)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Zehavi, M.: Maximum minimal vertex cover parameterized by vertex cover. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 589–600. Springer, Heidelberg (2015)
Acknowledgements
We thank anonymous referees for helpful comments. We also thank our colleagues David Manlove and Daniel Meister for discussions on upper domination. Part of this research was supported by the DFG, grant FE 560/6-1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Bazgan, C. et al. (2016). Upper Domination: Complexity and Approximation. In: Mäkinen, V., Puglisi, S., Salmela, L. (eds) Combinatorial Algorithms. IWOCA 2016. Lecture Notes in Computer Science(), vol 9843. Springer, Cham. https://doi.org/10.1007/978-3-319-44543-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-44543-4_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44542-7
Online ISBN: 978-3-319-44543-4
eBook Packages: Computer ScienceComputer Science (R0)