Abstract:
We study the computational complexity of the minimum dominating set problem on graphs restricted by forbidden induced subgraphs. We give some dichotomies results for the problem on graphs defined by any combination of forbidden induced subgraphs with at most four vertices, implying either an NP-Hardness proof or a polynomial time algorithm. We also extend the results by showing that dominating set problem remains NP-hard even when the graph has maximum degree three, it is planar and has no induced claw, induced diamond, induced K4 nor induced cycle of length 4, 5, 7, 8, 9, 10 and 11. © 2015 Elsevier B.V. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size |
Autor: | Lin, M.C.; Mizrahi, M.J. |
Filiación: | Instituto de Calculo, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
|
Palabras clave: | Algorithms; Complexity; Dominating set; Forbidden induced subgraphs; Algorithms; Computational complexity; Polynomial approximation; Complexity; Dominating set problems; Dominating sets; Domination problem; Forbidden induced subgraphs; Maximum degree; Minimum dominating set; Polynomial-time algorithms; Graph theory |
Año: | 2015
|
Volumen: | 197
|
Página de inicio: | 53
|
Página de fin: | 58
|
DOI: |
http://dx.doi.org/10.1016/j.dam.2015.02.010 |
Título revista: | Discrete Applied Mathematics
|
Título revista abreviado: | Discrete Appl Math
|
ISSN: | 0166218X
|
CODEN: | DAMAD
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v197_n_p53_Lin |
Referencias:
- Bertossi, A.A., Dominating sets for split and bipartite graphs (1984) Inf. Process. Lett., 19, pp. 37-40
- Boliac, R., Lozin, V., On the clique-width of graphs in hereditary classes (2002) ISAAC, pp. 44-54
- Booth, K.S., Johnson, J.H., Dominating sets in chordal graphs (1982) SIAM J. Comput., 11 (1), pp. 191-199
- Brandstädt, A., Engelfriet, J., Le, H., Lozin, V.V., Clique-width for 4-vertex forbidden subgraphs (2006) Theory Comput. Syst., 39 (4), pp. 561-590
- Chang, M.-S., Efficient algorithms for the domination problems on interval and circular-arc graphs (1998) SIAM J. Comput., 27, pp. 1671-1694
- Chao, H.S., Hsu, F.R., Lee, R.C.T., An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs (2000) Discrete Appl. Math., 102 (3), pp. 159-173
- Cooper, C., Klasing, R., Zito, M., Lower bounds and algorithms for dominating sets in web graphs (2005) Internet Math., 2, pp. 275-300
- Courcelle, B., Makowsky, J.A., Rotics, U., Linear time solvable optimization problems on graphs of bounded clique width (1999) Theory Comput. Syst., 33, pp. 125-150
- Dabrowski, K.K., Lozin, V., Raman, R., Ries, B., Colouring vertices of triangle-free graphs without forests (2012) Discrete Math., 312 (7), pp. 1372-1385
- Farber, M., Domination, independent domination, and duality in strongly chordal graphs (1984) Discrete Appl. Math., 7 (2), pp. 115-130
- Garey, M.R., Johnson, D.S., (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness, , W. H. Freeman & Co New York, NY, USA
- Gavril, F., Yannakakis, M., Edge dominating sets in graphs (1980) SIAM J. Appl. Math., 38 (3), pp. 364-372
- Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A., Domination in graphs applied to electric power networks (2002) SIAM J. Discrete. Math., 15, pp. 519-529
- Haynes, T.W., Hedetniemi, S.T., Slater, P.J., (1998) Fundamentals of Domination in Graphs
- Kloks, T., Kratsch, D., Müller, H., Finding and counting small induced subgraphs efficiently (2000) Inf. Process. Lett., 74 (3-4), pp. 115-121
- Kratsch, D., Domination and total domination on asteroidal triple-free graphs (2000) Discrete Appl. Math., 99 (1-3), pp. 111-123
- Lozin, V., Milanic, M., (2006) Domination in Graphs of Low Degree. Rutcor Research Report (RRR), , New Jersey 27
- Matheson, L.R., Tarjan, R.E., Dominating sets in planar graphs (1996) European J. Combin., 17 (6), pp. 565-568
- Müller, H., Brandstädt, A., The NP-completeness of steiner tree and dominating set for chordal bipartite graphs (1987) Theoret. Comput. Sci., 53, pp. 257-265
- Nicolai, F., Szymczak, T., Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs (2001) Networks, 37 (3), pp. 117-128
- Wu, J., Li, H., A dominating-set-based routing scheme in ad hoc wireless networks (2001) Telecommun. Syst., 18 (1-3), pp. 13-36
- Yannakakis, M., The complexity of the partial order dimension problem (1982) SIAM J. Algebr. Discrete Methods, 3 (3), pp. 351-358
- Zverovich, I.E., The domination number of (K <inf>p</inf>, P <inf>5</inf>) -free graphs (2003) Australas. J. Combin., pp. 95-100
Citas:
---------- APA ----------
Lin, M.C. & Mizrahi, M.J.
(2015)
. On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size. Discrete Applied Mathematics, 197, 53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010---------- CHICAGO ----------
Lin, M.C., Mizrahi, M.J.
"On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size"
. Discrete Applied Mathematics 197
(2015) : 53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010---------- MLA ----------
Lin, M.C., Mizrahi, M.J.
"On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size"
. Discrete Applied Mathematics, vol. 197, 2015, pp. 53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010---------- VANCOUVER ----------
Lin, M.C., Mizrahi, M.J. On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size. Discrete Appl Math. 2015;197:53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010