TY - GEN
T1 - Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
AU - Blanché, Alexandre
AU - Mizuta, Haruka
AU - Ouvrard, Paul
AU - Suzuki, Akira
N1 - Funding Information:
Partially supported by JSPS and MAEDI under the Japan-France Integrated Action Program (SAKURA). The first and third author is partially supported by ANR project GrR (ANR-18-CE40-0032). The second author is partially supported by JSPS KAK-ENHI Grant Number JP19J10042, Japan. The third author is partially supported by ANR project GraphEn (ANR-15-CE40-0009). The fourth author is partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP17K12636 and JP18H04091, Japan. Full version available at https://arxiv.org/abs/1906.05163.
Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - 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 d + s where d is the degeneracy and s is the upper bound of the output solution.
AB - 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 d + s where d is the degeneracy and s is the upper bound of the output solution.
KW - Combinatorial reconfiguration
KW - Dominating set
KW - Parameterized complexity
UR - http://www.scopus.com/inward/record.url?scp=85086222738&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086222738&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-48966-3_6
DO - 10.1007/978-3-030-48966-3_6
M3 - Conference contribution
AN - SCOPUS:85086222738
SN - 9783030489656
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 69
EP - 82
BT - Combinatorial Algorithms - 31st International Workshop, IWOCA 2020, Proceedings
A2 - Gasieniec, Leszek
A2 - Gasieniec, Leszek
A2 - Klasing, Ralf
A2 - Radzik, Tomasz
PB - Springer
T2 - 31st International Workshop on Combinatorial Algorithms, IWOCA 2020
Y2 - 8 June 2020 through 10 June 2020
ER -