On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
复制标题
论连通支配集重构的参数化复杂性
DOI：
10.1007/s00453-021-00909-5
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Siebertz, Sebastian
中科院分区：
文献类型：
--
作者：
Lokshtanov, Daniel;Mouawad, Amer E.;Panolan, Fahad;Siebertz, Sebastian
在一个决策问题的重构版本中，输入是的实例和两个可行的解决方案和T.我们的目标是确定是否存在一个一步一步的转换betweenSandT，使所有的中间步骤也构成可行的解决方案。本文研究了连通支配集重构问题（CDS-R）的参数化复杂性。在以前的工作中，已表明，由k参数化的支配集重构问题（DS-R），在重构序列中的支配集的最大允许大小，是固定参数易处理的所有图，不包括一个bicycle作为一个子图，对于一些常数。我们发现，额外的连通性约束使问题变得更加困难，即，thatCDS-RisW[1]-硬参数化，最大允许的大小的控制集加上长度的重新配置序列，已经在5-退化图。在积极的一面，我们表明，CDS-R参数是固定参数易处理的，事实上承认一个多项式核的平面图。
In a reconfiguration version of a decision problemthe input is an instance ofand two feasible solutionsSandT. The objective is to determine whether there exists a step-by-step transformation betweenSandTsuch that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of theConnected Dominating Set Reconfigurationproblem (CDS-R). It was shown in previous work that theDominating Set Reconfigurationproblem (DS-R) parameterized byk, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a bicliqueas a subgraph, for some constant. We show that the additional connectivity constraint makes the problem much harder, namely, thatCDS-RisW[1]-hard parameterized by, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show thatCDS-Rparameterized bykis fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.
登录
查看更多内容
DOI：
10.1137/16m1065288
发表时间：
2014
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
A. E. Mouawad;N. Nishimura;Vinayak Pathak;Venkatesh Raman
通讯作者：
Venkatesh Raman
NP 完全谜题综述
DOI：
10.3233/icg-2008-31103
发表时间：
2008
期刊：
J. Int. Comput. Games Assoc.
影响因子：
--
作者：
G. Kendall;A. Parkes;Kristian Spoerer
通讯作者：
Kristian Spoerer
DOI：
10.1007/10692760_1
发表时间：
1998-06
期刊：
--
影响因子：
--
作者：
B. Courcelle;J. Makowsky;Udi Rotics
通讯作者：
B. Courcelle;J. Makowsky;Udi Rotics
在稀疏图类上使用结构参数进行核化
DOI：
10.1007/978-3-642-40450-4_45
发表时间：
2013
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Jakub Gajarský;Petr Hlinený;Jan Obdrzálek;Sebastian Ordyniak;Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
通讯作者：
Somnath Sikdar
DOI：
10.1145/3051095
发表时间：
2013-11
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
Martin Grohe;S. Kreutzer;S. Siebertz
通讯作者：
Martin Grohe;S. Kreutzer;S. Siebertz