Cargando…

Decremental Optimization of Dominating Sets Under the Reconfiguration Framework

Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the property that the set forms a dominating set of bounded size. This can be seen as the optimization variant of the domin...

Descripción completa

Detalles Bibliográficos
Autores principales: Blanché, Alexandre, Mizuta, Haruka, Ouvrard, Paul, Suzuki, Akira
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7254914/
http://dx.doi.org/10.1007/978-3-030-48966-3_6
_version_ 1783539634691637248
author Blanché, Alexandre
Mizuta, Haruka
Ouvrard, Paul
Suzuki, Akira
author_facet Blanché, Alexandre
Mizuta, Haruka
Ouvrard, Paul
Suzuki, Akira
author_sort Blanché, Alexandre
collection PubMed
description Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the property that the set forms a dominating set of bounded size. This can be seen as the optimization variant of the dominating set reconfiguration problem, where two dominating sets are given and the question is merely whether they can be reached from one another through elementary operations. We show that this problem is PSPACE-complete, even if the input graph is a bipartite graph, a split graph, or has bounded pathwidth. On the positive side, we give linear-time algorithms for cographs, trees and interval graphs. We also study the parameterized complexity of this problem. More precisely, we show that the problem is W[2]-hard when parameterized by the upper bound on the size of an intermediary dominating set. On the other hand, we give fixed-parameter algorithms with respect to the minimum size of a vertex cover, or [Formula: see text] where d is the degeneracy and s is the upper bound of the output solution.
format Online
Article
Text
id pubmed-7254914
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72549142020-05-28 Decremental Optimization of Dominating Sets Under the Reconfiguration Framework Blanché, Alexandre Mizuta, Haruka Ouvrard, Paul Suzuki, Akira Combinatorial Algorithms Article Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the property that the set forms a dominating set of bounded size. This can be seen as the optimization variant of the dominating set reconfiguration problem, where two dominating sets are given and the question is merely whether they can be reached from one another through elementary operations. We show that this problem is PSPACE-complete, even if the input graph is a bipartite graph, a split graph, or has bounded pathwidth. On the positive side, we give linear-time algorithms for cographs, trees and interval graphs. We also study the parameterized complexity of this problem. More precisely, we show that the problem is W[2]-hard when parameterized by the upper bound on the size of an intermediary dominating set. On the other hand, we give fixed-parameter algorithms with respect to the minimum size of a vertex cover, or [Formula: see text] where d is the degeneracy and s is the upper bound of the output solution. 2020-04-30 /pmc/articles/PMC7254914/ http://dx.doi.org/10.1007/978-3-030-48966-3_6 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Blanché, Alexandre
Mizuta, Haruka
Ouvrard, Paul
Suzuki, Akira
Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
title Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
title_full Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
title_fullStr Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
title_full_unstemmed Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
title_short Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
title_sort decremental optimization of dominating sets under the reconfiguration framework
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7254914/
http://dx.doi.org/10.1007/978-3-030-48966-3_6
work_keys_str_mv AT blanchealexandre decrementaloptimizationofdominatingsetsunderthereconfigurationframework
AT mizutaharuka decrementaloptimizationofdominatingsetsunderthereconfigurationframework
AT ouvrardpaul decrementaloptimizationofdominatingsetsunderthereconfigurationframework
AT suzukiakira decrementaloptimizationofdominatingsetsunderthereconfigurationframework