Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
复制标题
在重新配置框架下的主导集的减少优化
DOI：
10.1007/978-3-030-48966-3_6
复制
发表时间：
2020-04-30
期刊：
影响因子：
--
通讯作者：
Suzuki A
中科院分区：
文献类型：
--
作者：
Blanché A;Mizuta H;Ouvrard P;Suzuki A
给定一个控制集，通过初等运算我们能找到小多少的控制集？在这里，我们进行迭代顶点添加和删除，同时保持该集形成有界大小的支配集的属性。这可以被看作是支配集重构问题的优化变体，其中给出了两个支配集，问题仅仅是它们是否可以通过初等运算从彼此到达。我们表明，这个问题是PSPACE完全的，即使输入图是一个二分图，分裂图，或有界的路宽。在积极的一面，我们给出了线性时间算法的共图，树和区间图。我们还研究了这个问题的参数化复杂性。更确切地说，我们证明了当用中介支配集的大小上界参数化时，问题是W[2]-困难的。另一方面，我们给出了固定参数算法的顶点覆盖的最小尺寸，或其中d是退化和s是输出解的上界。
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 where d is the degeneracy and s is the upper bound of the output solution.
登录
查看更多内容
影响因子：
1.1
作者：
Chen, Jianer;Kanj, Iyad A.;Xia, Ge
通讯作者：
Xia, Ge
影响因子：
0.5
作者：
BERTOSSI, AA
通讯作者：
BERTOSSI, AA
影响因子：
1.1
作者：
Ito, Takehiro;Demaine, Erik D.;Uno, Yushi
通讯作者：
Uno, Yushi
影响因子：
1.3
作者：
Lokshtanov, Daniel;Mouawad, Amer E.
通讯作者：
Mouawad, Amer E.
影响因子：
1.1
作者：
Lokshtanov, Daniel;Mouawad, Amer E.;Saurabh, Saket
通讯作者：
Saurabh, Saket