An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
复制标题
DOI：
10.1007/s00224-022-10076-x
复制
发表时间：
2020-12
影响因子：
0.5
通讯作者：
Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
中科院分区：
文献类型：
--
作者：
Yuuki Aoike;Tatsuya Gima;T. Hanaka;Masashi Kiyomi;Yasuaki Kobayashi;Yusuke Kobayashi;Kazuhiro Kurita;Y. Otachi
表示一个连通图，它不包含K4−e作为次项。给定一个图G=(V，E)和一个整数≥ 0，仙人掌顶点删除(也称为钻石命中集)是决定G是否有一个大小的顶点集的问题，该顶点集的移除留下了一片仙人掌森林。这个问题以前最好的确定性参数化算法是由Bonnet等人提出的。[WG]，它运行在时间26ounO(1)中，其中是G的顶点数。在本文中，我们设计了一个确定性的仙人掌顶点删除算法，运行时间为17.64knO(1)。作为算法的一个几乎直接的应用，我们还给出了一个确定的17.64knO(1)时间的偶圈遍历算法，该算法改进了Misra等人提出的确定性参数化算法的运行时间50knO(1)。[工作组]。
Acactusis a connected graph that does not containK4−eas a minor. Given a graphG= (V,E) and an integerk≥ 0,Cactus Vertex Deletion(also known asDiamond Hitting Set) is the problem of deciding whetherGhas a vertex set of size at mostkwhose removal leaves a forest of cacti. The previously best deterministic parameterized algorithm for this problem was due to Bonnet et al. [WG ], which runs in time 26knO(1), wherenis the number of vertices ofG. In this paper, we design a deterministic algorithm forCactus Vertex Deletion, which runs in time 17.64knO(1). As an almost straightforward application of our algorithm, we also give a deterministic 17.64knO(1)-time algorithm forEven Cycle Transversal, which improves the previous running time 50knO(1)of the known deterministic parameterized algorithm due to Misra et al. [WG ].