A boundary property for upper domination. (English) Zbl 1392.68195
Mäkinen, Veli (ed.) et al., Combinatorial algorithms. 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17–19, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-44542-7/pbk; 978-3-319-44543-4/ebook). Lecture Notes in Computer Science 9843, 229-240 (2016).
Summary: An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as \(P_4\)-free graphs or \(2K_2\)-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating difficult instances of the problem from polynomially solvable ones consists of the so called boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem.
For the entire collection see [Zbl 1343.68012].
For the entire collection see [Zbl 1343.68012].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | 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) · Zbl 1391.05240 · doi:10.1007/978-3-319-12691-3_20 |
| [2] | Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Appl. Math. 132, 17–26 (2003) · Zbl 1029.05140 · doi:10.1016/S0166-218X(03)00387-1 |
| [3] | Alekseev, V.E., Korobitsyn, D.V., Lozin, V.V.: Boundary classes of graphs for the dominating set problem. Discrete Math. 285, 1–6 (2004) · Zbl 1121.05081 · doi:10.1016/j.disc.2004.04.010 |
| [4] | Alekseev, V.E., Boliac, R., Korobitsyn, D.V., Lozin, V.V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219–236 (2007) · Zbl 1143.68058 · doi:10.1016/j.tcs.2007.09.013 |
| [5] | Cheston, G.A., Fricke, G., Hedetniemi, S.T., Jacobs, D.P.: On the computational complexity of upper fractional domination. Discrete Appl. Math. 27(3), 195–207 (1990) · Zbl 0717.05068 · doi:10.1016/0166-218X(90)90065-K |
| [6] | 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) · Zbl 0471.05051 · doi:10.1016/0012-365X(81)90268-5 |
| [7] | Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125–150 (2000) · Zbl 1009.68102 · doi:10.1007/s002249910009 |
| [8] | Courcelle, B., Olariu, S.: Upper bounds to the clique-width of a graph. Discrete Appl. Math. 101, 77–114 (2000) · Zbl 0958.05105 · doi:10.1016/S0166-218X(99)00184-5 |
| [9] | 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, pp. 437–457. Academic Press, New York (1987) · Zbl 0643.68093 · doi:10.1016/B978-0-12-386870-1.50030-7 |
| [10] | Jacobson, M.S., Peters, K.: Chordal graphs and upper irredundance, upper domination and independence. Discrete Math. 86(1–3), 59–69 (1990) · Zbl 0744.05063 · doi:10.1016/0012-365X(90)90349-M |
| [11] | Kamiński, M., Lozin, V., Milanič, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157, 2747–2761 (2009) · Zbl 1211.05165 · doi:10.1016/j.dam.2008.08.022 |
| [12] | Korobitsyn, D.V.: On the complexity of determining the domination number in monogenic classes of graphs. Diskretnaya Matematika 2(3), 90–96 (1990). (in Russian, translation in Discrete Math. Appl. 2(2), 191–199 (1992)) · Zbl 0729.05047 |
| [13] | Korpelainen, N., Lozin, V.V., Malyshev, D.S., Tiskin, A.: Boundary properties of graphs for algorithmic graph problems. Theor. Comput. Sci. 412, 3545–3554 (2011) · Zbl 1222.05243 · doi:10.1016/j.tcs.2011.03.001 |
| [14] | Korpelainen, N., Lozin, V., Razgon, I.: Boundary properties of well-quasi-ordered sets of graphs. Order 30, 723–735 (2013) · Zbl 1276.05062 · doi:10.1007/s11083-012-9272-2 |
| [15] | Lozin, V.V.: Boundary classes of planar graphs. Comb. Probab. Comput. 17, 287–295 (2008) · Zbl 1166.05016 · doi:10.1017/S0963548307008814 |
| [16] | Lozin, V., Milanič, M.: Critical properties of graphs of bounded clique-width. Discrete Math. 313, 1035–1044 (2013) · Zbl 1262.05120 · doi:10.1016/j.disc.2013.01.008 |
| [17] | Lozin, V., Purcell, C.: Boundary properties of the satisfiability problems. Inf. Process. Lett. 113, 313–317 (2013) · Zbl 1287.68058 · doi:10.1016/j.ipl.2013.01.022 |
| [18] | Lozin, V., Rautenbach, D.: On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18, 195–206 (2004) · Zbl 1081.05098 · doi:10.1137/S0895480102419755 |
| [19] | Lozin, V., Zamaraev, V.: Boundary properties of factorial classes of graphs. J. Graph Theor. 78, 207–218 (2015) · Zbl 1309.05150 · doi:10.1002/jgt.21799 |
| [20] | Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35, 167–170 (1992) · Zbl 0769.05053 · doi:10.1016/0166-218X(92)90041-8 |
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.
