On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size

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-Hard...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Mizrahi, M.J.
Formato: JOUR
Materias:
Algorithms
Complexity
Dominating set
Forbidden induced subgraphs
Computational complexity
Polynomial approximation
Dominating set problems
Dominating sets
Domination problem
Maximum degree
Minimum dominating set
Polynomial-time algorithms
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v197_n_p53_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0166218X_v197_n_p53_Lin
record_format dspace
spelling todo:paper_0166218X_v197_n_p53_Lin2023-10-03T15:03:43Z On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size Lin, M.C. Mizrahi, M.J. 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 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. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v197_n_p53_Lin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
Lin, M.C.
Mizrahi, M.J.
On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
topic_facet 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
description 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.
format JOUR
author Lin, M.C.
Mizrahi, M.J.
author_facet Lin, M.C.
Mizrahi, M.J.
author_sort Lin, M.C.
title On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_short On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_full On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_fullStr On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_full_unstemmed On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_sort on the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
url http://hdl.handle.net/20.500.12110/paper_0166218X_v197_n_p53_Lin
work_keys_str_mv AT linmc onthecomplexityoftheminimumdominationproblemrestrictedbyforbiddeninducedsubgraphsofsmallsize
AT mizrahimj onthecomplexityoftheminimumdominationproblemrestrictedbyforbiddeninducedsubgraphsofsmallsize
_version_ 1807320716994936832

Ejemplares similares